java - 获取两个字符串数组的所有可能组合

Question

我有一个两个字符串数组:

A("0", "1", "2", "3", "4", "5", "6", "7")
B("a", "b", "c", "d", "e")

排列以发现可能组合的数量:

[((8!)/(8-5)!)*((3!)/(3-2)!)]*[(7!)/((2!)*(7-2)!)]
40320 * 21 = 846720

如何使用 A 的 5 个元素和 B 的 2 个元素获得两个数组之间的所有组合，而不重复？

为此，我编写了一个代码来检索所有“组合键”:

package wodlist;

import java.util.ArrayList;
import java.util.List;

public class GenerateKey {

 static void perm1(String c0, int n0, String c1, int n1, String s, 
 List<String> result) {
    if (n0 < 0 || n1 < 0)
        return;
    else if (n0 == 0 && n1 == 0)
        result.add(s);
    else {
        perm1(c0, n0 - 1, c1, n1, s + c0, result);
        perm1(c0, n0, c1, n1 - 1, s + c1, result);
    }

  }

  static List<String> perm(String c0, int n0, String c1, int n1) {
    List<String> result = new ArrayList<>();
    perm1(c0, n0, c1, n1, "", result);
    return result;
  }
}

当调用函数perm("A", 5, "B", 2)时，我将得到与此类似的结果::

[AAAAABB, AAAABAB, AAAABBA, AAABAAB, AAABABA, AAABBAA, AABAAAB, AABAABA, AABABAA, AABBAAA, ABAAAAB, ABAAABA, ABAABAA, ABABAAA, ABBAAAA, BAAAAAB, BAAAABA, BAAABAA, BAABAAA, BABAAAA, BBAAAAA]

这就是“键”，但是如何使用 A 的 5 个元素和 B 的 2 个元素获得每个键的所有组合？

例如:

AAAAABB = {0,2,3,4,5,a,b}, {0,2,3,4,5,a,c}, {0,2,3,4,5,a,d}...
AAAABAB = ...

我制作了这个示例，它具有相同的“逻辑”，但我无法用它复制，因为在其中我知道可能的组合的数量。如果我有两个数组，我将使用每个数组的字符数量，但另一个问题是我知道每个“键”的可能组合数量。关于上面的问题我不知道。

    String[] A = new String[]{"1","2","3"};
    String[] B = new String[]{"a","b","c"};
    //key
    String[] AAB = new String[18];
    String[] ABA = new String[18];
    String[] BAA = new String[18];
    //result
    String[] S = new String[54];
    //
    //[A0,A1,B]
    int aabIndex = 0, abaIndex = 0, baaIndex=0;
    for (int a0Index = 0; a0Index < 3; a0Index++){
        for (int a1Index = 0; a1Index < 3; a1Index++) {
            // skip when A0 == A1
            if (a0Index == a1Index) continue;
            // scroll through b
            for(int bIndex = 0; bIndex < 3; bIndex++){
                AAB[aabIndex++] = A[a0Index] + A[a1Index] + B[bIndex];
                ABA[abaIndex++] = A[a0Index] + B[bIndex] + A[a1Index];
                BAA[baaIndex++] = B[bIndex] + A[a0Index] + A[a1Index];
            }
        }
    }

排列得到上述结果:

[Arrangement(3,2)*Arrangement(3,1)]*Combination(3,2)
[(3!/(3-2)!)*(3!/(3-1)!]*[3!/(2!*(3-2)!) = 
[6 * 3] * 3 = 54

有人可以帮我吗？

Answer 1

试试这个:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static java.util.stream.Collectors.toList;

public class Perm2 {

  public static void main(String[] args) {
    List<String> listA = Arrays.asList("1", "2", "3");
    List<String> listB = Arrays.asList("a", "b", "c");

    List<String> result = perm2(listA, 2, listB, 1);
    result.forEach(System.out::println);
    System.out.println("--- count = " + result.size());
  }

  private static List<String> perm2(List<String> listA, int numA, List<String> listB, int numB) {
    if (numA == 0 && numB == 0) return Collections.singletonList("");

    List<String> forSelect = new ArrayList<>();
    if (numA > 0) forSelect.addAll(listA);
    if (numB > 0) forSelect.addAll(listB);

    List<String> result = new ArrayList<>();
    for (String elem : forSelect) {
      List<String> newListA = without(listA, elem);
      int newNumA = numA - (listA.contains(elem) ? 1 : 0);
      List<String> newListB = without(listB, elem);
      int newNumB = numB - (listB.contains(elem) ? 1 : 0);
      result.addAll(
            perm2(newListA, newNumA, newListB, newNumB).stream()
                  .map(s -> elem + s)
                  .collect(toList()));
    }
    return result;
  }

  private static List<String> without(List<String> list, String elem) {
    return list.stream().filter(e -> e != elem).collect(toList());
  }

}

我假设 list 和 list 中的所有元素都是不同的，并且要选择的元素数量在 0..length 范围内。