Finding all the "move combinations" to partition an array

[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

List<T> stuff;

that I've populated with values. Given some

int k;

that has a value and has

0 < k <= stuff.Length

I want to populate a structure

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.

 

[Stephen Tashi]

Example: The array {A,B,C} of size N=3 and I want all the move combinations that make it into K=1 subgroups.

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 into 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 ?

 

[SlurrerOfSpeech]

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 into 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 ?

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

 

[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.

 

[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

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[] line1 = LineToIntArray(Console.ReadLine());
        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)
        {
            int[] line = LineToIntArray(Console.ReadLine());
            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[end].Add(mines[start]);
                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);
    }
}