Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jul 31, 2016 #1
    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. jcsd
  3. Jul 31, 2016 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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 ?
  4. Jul 31, 2016 #3
    In the problem I'm trying to solve, the order of the moves does not matter.
  5. Jul 31, 2016 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
  6. Jul 31, 2016 #5
    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[] 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 })
                foreach(var move in combo)
                    int start = mines.IndexOf(move.Item1),
                          end = mines.IndexOf(move.Item2);
                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);
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted