# C/++/# Finding all the "move combinations" to partition an array

Tags:
1. Jul 31, 2016

### SlurrerOfSpeech

of size N into an K subgroups. I've been trying for hours to do this and still haven't found a solution.

Example: The array {A,B,C} of size N=3 and I want all the move combinations that make it into K=1 subgroups. The only such subgroup is the one with all the elements, and I can get that with the move combinations

B -> A, C -> A
C -> A, B -> A
A -> B, C -> B
C -> B, A -> B
A -> C, B -> C
B -> C, A -> C

If K=2 then the move combinations are

A -> B (now we have { {A,B}, {C} })
B -> A (now we have { {A,B}, {C} })
B -> C (now we have { {A}, {B,C} })
C -> B (now we have { {A}, {B,C} })
A -> C (now we have { {B}, {A,C} })
C -> A (now we have { {B}, {A,C} })

Hope that makes sense.

To be even more concrete, in terms of C#, what I have is a list

Code (Text):

List<T> stuff;

that I've populated with values. Given some

Code (Text):

int k;

that has a value and has

Code (Text):

0 < k <= stuff.Length

I want to populate a structure

Code (Text):

List<List<Tuple<T,T>>> partitions;

that represents all the move combinations. Can't figure out how to write this algorithm.

Let me know if I need to provide more clarity.

2. Jul 31, 2016

### Stephen Tashi

I think you mean "partition it into K=1 subsets"

If the set S has N things, perhaps you should start with finding the moves that partition it into K = N-1 subsets.

To partition S in to N-2 subsets, you can look at each of the partitions from the previous step and examine what moves would reduce the number of sets in the partition by 1.

I don't know how you are defining "different" moves. Does the order in which the moves are made matter? For example, is A->B, C->E, F->G the "same" as C->E, A->B, F->G ? Is A->B, B->C, C->D the same move as A->D, B->D ?

3. Jul 31, 2016

### SlurrerOfSpeech

In the problem I'm trying to solve, the order of the moves does not matter.

4. Jul 31, 2016

### Stephen Tashi

I'm suggesting you start the algorithm at K = N-1 instead of K = 1.

To partition {A,B,C,D} into 3 sets, you have to "move" one element to another. So you generate the possible ways of moving one element to another and you store the resulting partitions.

Then you consider how to partition {A,B,C,D} into 2 sets. Look at each partition from the previous step and find all the ways of eliminating one of its subsets. For example, if the partition from the previous step is {{A,B},C,D} then to eliminate 1 of the subsets in the partition, you must move the subset (completely) to another subset. For example, you might move {A,B} to {C}. Or you might move {C} to {D}.

Depending on how you define on sequence of moves to be the same or different than another, you may have to make a pass through all the move sequences you have generated and eliminate the duplicates.

5. Jul 31, 2016

### SlurrerOfSpeech

Ok, I might as well show the context of the problem I'm solving. In fact, I have a solution but it is failing some of the unit tests due to timing out. I need to reduce the number of operations involved.

The problem is this one from HackerRank and my solution is

Code (Text):

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

static class Extensions
{
// ripped from http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
}

class Mine
{
public int Distance { get; set; } // from river
public int Gold { get; set; } // in tons
}

class Solution
{
static void Main(String[] args)
{
// helper function for reading lines
Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

int N = line1[0], // # of mines
K = line1[1]; // # of pickup locations

// Populate mine info
List<Mine> mines = new List<Mine>();
for(int i = 0; i < N; ++i)
{
mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
}

// helper function for checking whether a move combination ends up
// forming K groups
Func<IEnumerable<Tuple<Mine,Mine>>, bool> FormsKGroups = combo =>  {
var groups = mines.Select(mine => new List<Mine>() { mine })
.ToList();
foreach(var move in combo)
{
int start = mines.IndexOf(move.Item1),
end = mines.IndexOf(move.Item2);
groups[start].Remove(mines[start]);
}
return groups.Count(g => g.Count > 0) == K;
};

// Get all move combinations that form K groups
var moveCombos = mines.SelectMany(m => mines, (m1, m2) => Tuple.Create(m1, m2))
.Where(tuple => !tuple.Item1.Equals(tuple.Item2)) // we have all 2^N ordered pairs of mines
.Combinations(N - K) // all combinations of length (N - K) of those pairs
.Where(x => true); // that form K groups

// helper function for calculating the cost of a sequence of moves
Func<IEnumerable<Tuple<Mine,Mine>>, int> MovesCost = (moves) =>
moves.Aggregate(0, (sum, move) =>
sum + Math.Abs(move.Item1.Distance - move.Item2.Distance) * move.Item1.Gold);

// calculate min cost and print result
int mincost = moveCombos.Min(MovesCost);
Console.WriteLine(mincost);
}
}