组合发电机

Question

我有一个多维数组，其大小是动态的。

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

我需要生成这样的组合，每个组合的长度必须介于 1-array.length 之间，并且每个组合最多可以包含一行中的一个元素。如果使用一行中的一列，则该行中的其他列不能用于该组合。

例如长度为 1 的组合是：

长度为 2 的组合是：

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

目前我只能得到与 length = array.length 的组合，但我需要从 1 到 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

你喜欢1个字母的变量名吗...？ :D 我什至不知道它现在是如何工作的。它使用位掩码来查找长度为 n 的子数组的每个组合；然后它使用一些 mod 数学从每个子数组中找到 1 的每个组合；然后它吐出那个数字。排序顺序不理想。

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

好的，如果我明白你的问题，那么让我澄清一下。

你想要一些 n 组的所有组合，在任何组合中你只能从一组中取出一个元素。并且组合的长度可以取值1到n。

所以基本上这是可行的算法。

看到每个集合都有一个选项，它可以在组合中，也可以不在组合中。
如果任何集合在组合中，那么它有 p 个选项（p 是集合的长度）到 select 它的任何元素。

所以基本上我们得到 (2^arraylength -1(未采用))*(P) P=每个集合中元素的数量这么多组合。

所以基本上你要做的就是编写一个递归函数，给它参数，比如级别、len。

写一个for循环，让len从1到n；现在对于 i [1,len] 的每个值递归函数将按长度 len 的顺序打印所有组合。

所以你会得到长度为1到arraylength()的所有组合这是我编写的代码，它不可运行，但它是我的算法的更易于理解的版本。

这就是您可以做的事情。

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

如果有人正在寻找更灵活的解决方案，我会使用流和减少来创建这个解决方案。您可以在运行此处 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]
        // ]

    }
}

组合发电机

Combination Generator

java

recursion

combinations

loops

while-loop