Combination Generator

Question

I have a multi dimensional array whose size is dynamic.

String[][] array=new String[][]{{"1","2","3"},{"4","5","6"},{"7","8","9"},{"10","11","12"} };

I need to generate combinations such like that every combination length must lies between 1-array.length and every combination can have maximum one element from a row. if a column from a row is used then no other column from that row can be used in that combination.

for example combinations with length 1 are :

1
2
3
4
5
6
7
8
9
10
11
12

combination with length 2 are :

1,4
1,5
1,6
1,7
1,8
1,9
1,10
1,11
1,12

Currently i am only been able to get combination with length = array.length but i need length from 1 to array.length

private String[][] generateCombinations(String[]... arrays) throws Throwable       {
    if (arrays.length == 0) {
        return new String[][]{{}};
    }
    int num = 1;
    for (int i = 0; i < arrays.length; i++) {
        num *= arrays[i].length;
    }

    String[][] result = new String[num][arrays.length];
    // array containing the indices of the Strings
    int[] combination = new int[arrays.length];

    for (int i = 0; i < num; i++) {
        String[] comb = result[i];
        // fill array
        for (int j = 0; j < arrays.length; j++) {
            comb[j] = arrays[j][combination[j]];
        }

        // generate next combination
        for (int j = 0; j < arrays.length; j++) {
            int n = ++combination[j];
            if (n >= arrays[j].length) {
                // "digit" exceeded valid range -> back to 0 and continue incrementing
                combination[j] = 0;
            } else {
                // "digit" still in valid range -> stop
                break;
            }
        }
    }
    return result;
}

Answer 1

Do you like 1 letter variable names...? :D I don't even know how it works now. It uses bit masks to find every combination of subarrays of length n; then it uses some mod math to find every combination of 1 from each subarray; then it spits out that number. Sort order isn't ideal.

public class Perms {
    private static String[][] array = new String[][] {
        { "1", "2", "3" },
        { "4", "5", "6" },
        { "7", "8", "9" },
        { "10", "11", "12" }
    };
    private static int combinationLength = 2;
    public static void main(String[] args) {
        // Get combinations of subarrays
        for (int i = 0; i < Math.pow(2, array.length); ++i) {
            int c = 0;
            for (int j = 1; j <= Math.pow(2, array.length); j <<= 1)
                if ((i & j) != 0)
                    ++c;
            if (c == combinationLength) {
                String[][] maskedArray = new String[combinationLength][];
                for (int l = 1, j = 0, k = 0; l <= Math.pow(2, array.length); l <<= 1, ++j)
                    if ((i & l) != 0) {
                        maskedArray[k] = array[j];
                        ++k;
                    }
                // Get combinations of one element per subarray
                int l = 1;
                for (int j = 0; j < maskedArray.length; ++j)
                    l *= maskedArray[j].length;
                for (int j = 0; j < l; ++j) {
                    String s = "";
                    int m = j;
                    for (int k = maskedArray.length-1; k >= 0; --k) {
                        s = maskedArray[k][m % maskedArray[k].length] + "," + s;
                        m /= maskedArray[k].length;
                    }
                    // Spit out a result
                    System.out.println(s.substring(0, s.length()-1));
                }
            }
        }
    }
}

Answer 2

Ok if I am getting what you are asking then let me clarify.

You want all the combination of some n sets where in any combination you can take only one element from one set. And the length of the combination can be of value 1 to n.

So basically this is the algorithm that would work.

1. See each set has an option it can either be in the combination or it may not be in the combination.
2. And if any set is in the combination then it has p options(p being the length of the set) to select any of its element.

So basically we get (2^arraylength -1(Non taken))*(P) P=number of elements in each set these many combinations.

So basically what you do is write a recursive function give it parameters like level, len.

Write a for loop so that len would go from 1 to n; now for each value of i [1,len] the recursive function would print all the combination in order of length len.

So you will get all the combination of length 1 to arraylength() this is a code that I wrote it is not runnable but it a more understandable version of my algo.

So here is what you can do.

int main()
{
  string s=" ";
  for(int i=0;i<=array.length;++i)
    {
      print-recur(array,s,arra.length,i,3,0);
    }
  return 0;
}

void print-recur(string array[][],string s[],int arlen,int len,int    p,int level)
{
  if(level>aralen)
    return ;
  else
    {
      if(len>0)
    {
      //this is not taking this level
      if(len>aralen-level)
        print-recur(a,s,arlen,len,p,level+1);
      //the for loop is when the level is in the combination
      for(i=0;i<p;++i)
        {
          s+=array[level][i];
          print-recur(a,s,arlen,len-1,p,level+1);
          str.erase( str.end()-1 );
        }
    }
      else
    cout<<s<<endl;
    }
}

Answer 3

If someone is searching for some more flexible solution, I create this one using stream and reduce. You can see it running here https://ideone.com/sSRrY3.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Combination {
    private List<List<List<String>>> pairs = new ArrayList<>();

    public Combination( List<String> elements ) {
        this.pairs = createPairsFromElements( elements );
    }

    private Combination() {
    }

    public static Combination createFromPairs( String[][] arrPairs ) {
        Combination combination = new Combination();
        combination.pairs = createPairsFromArrayPairs(arrPairs);
        return combination;
    }

    /**
     * Create the pairs based on the String[][]
     *
     * Add the empty option at the beginner of each group
     * Create the Lists and group them again
     *
     * @param arrPairs
     * @return pairs
     */
    private static List<List<List<String>>> createPairsFromArrayPairs( String[][] arrPairs ) {
        List<List<List<String>>> pairs = new ArrayList<>();

        for ( String[] groupValue: arrPairs ) {

            List<List<String>> listGroupValue = new ArrayList<>();

            /* add the empty value to the pairs */
            listGroupValue.add(Arrays.asList());

            for ( String value: groupValue ) {

                List<String> listValue = Arrays.asList( value );
                listGroupValue.add( listValue );

            }

            pairs.add( listGroupValue );
        }
        return pairs;

    }

    /**
     * Convert the string list "a", "b", "c" to
     * this:
     * [
     *  [ [], [a] ], [ [], [b] ], [ [], [c] ]
     * ]
     *
     * @param elements List of values to the collection
     * @return pairs
     */
    private static List<List<List<String>>> createPairsFromElements( List<String> elements ) {
        return elements.stream().map(
                (String value) -> {
                    List<List<String>> values = Arrays.asList(
                            Arrays.asList(),            // immutable empty list
                            Arrays.asList( value )      // immutable atomic list
                    );
                    return values;
                }
        ).collect(Collectors.toList());
    }

    /**
     * Get the combination without restriction
     *
     * @param size
     * @return
     */
    public List<List<String>> getCombination( int size ) {
        return this.getCombination( size, false );
    }

    /**
     /*
     * Combine every pair of elements creating a big list
     * [ [], [b] ] x [ [], [a] ] = [ ([] + []), ([] + [a]), ([b] + []), ([b] + [a])) ] =
     * [ [], [a], [b], [a, b] ]
     * This keep working until add all elements.
     *
     * We filter to remove the combinations that are bigger than the max size
     *
     * @param size Max size of each result list
     * @param restricted Should be exactly the received size.
     * @return List of combinations
     */
    public List<List<String>> getCombination( int size, boolean restricted ) {

        List<List<String>> result = pairs.parallelStream().reduce(
            new ArrayList<>(),
            (acc,current) -> {
                if( acc.size() == 0 ) {
                    return current;
                }

                List<List<String>> combinations = new ArrayList<>();

                current.stream().forEach(
                    (List<String> valueCurrent ) -> acc.stream().forEach(
                        (List<String> valueAcc) -> {
                            List<String> combination = new ArrayList<>();
                            combination.addAll( valueAcc );
                            combination.addAll( valueCurrent );
                            if( combination.size() <= size ) {
                                combinations.add( combination );
                            }
                        }
                    )
                );
                return combinations;
            }
        );

        if( ! restricted ) {
            return result;
        }

        /* if the combination is size restricted, filter only elements with the exactly size */
        return result.stream().filter( combination -> combination.size() == size ).
                collect(Collectors.toList());
    }
}

public class Main {

    public static void main( String[] param ) {

        Combination combination = new Combination(Arrays.asList("A","B","C","D","E"));

        /* show all the combinations from 0 to 3 elements */
        System.out.println( combination.getCombination(3));
        // [
        //  [],
        //  [A],
        //  [B], [A, B],
        //  [C], [A, C], [B, C], [A, B, C],
        //  [D], [A, D], [B, D], [A, B, D], [C, D], [A, C, D], [B, C, D],
        //  [E], [A, E], [B, E], [A, B, E], [C, E], [A, C, E], [B, C, E], [D, E], [A, D, E], [B, D, E], [C, D, E]
        // ]

        /* show all the combinations with exactly 4 elements */
        System.out.println( combination.getCombination(4, true));
        // [
        //   [A, B, C, D],
        //   [A, B, C, E],
        //   [A, B, D, E],
        //   [A, C, D, E],
        //   [B, C, D, E]
        // ]

        Combination other = Combination.createFromPairs(
                new String[][]{{"1","2","3"},{"4","5","6"},{"7","8","9"},{"10","11","12"} }
        );

        /* show all the combinations with exactly 3 elements */
        System.out.println( other.getCombination(3, true));
        // [
        //  [1, 4, 7], [2, 4, 7], [3, 4, 7], [1, 5, 7] ...
        //  ...  [3, 9, 12], [4, 9, 12], [5, 9, 12], [6, 9, 12]
        // ]

    }
}