两个数组的递归组合项（非空或重复），使用 Java

Question

我有两个数组（长度相同），大小可变。

为了做最简单的例子，我有两个长度为 3 的数组。

Persons -> P1, P2, P3
Seats -> Sa, Sb, Sc

我需要生成所有组合Cn

如果 P1 人带 Sa, 有可能是：

人 P2 拿 Sb 然后 P3 会拿 Sc。组合将是 P1Sa, P2Sb, P3Sc。
或人 P2 拿 Sc 然后 P3 将拿 Sb。组合将是 P1Sa, P2Sc, P3Sb.

现在这里是所有可能的组合。

C0 -> P1Sa, P2Sb, P3Sc
C1 -> P1Sa, P2Sc, P3Sb
C2 -> P1Sb, P2Sa, P3Sc
C3 -> P1Sb, P2Sc, P3Sa
C4 -> P1Sc, P2Sa, P3Sb
C5 -> P1Sc, P2Sb, P3Sa

这是我的糟糕设计。

  private void recursiveSeatPerson(String c, List<String> p, List<String> s) {
    if (p.size() > 1) {
      for (int i = 0; i < s.size(); i++) {
        String combination = p.get(0)+s.get(i) + ", " + c;
        System.out.print(combination);

        List<String> new_s = new ArrayList<>();
        for (int index_s = 0; index_s < s.size(); index_s++) {
          if (index_s != i) {
            new_s.add(s.get(i));
          }
        }
        List<String> new_p = new ArrayList<>();
        for (int index_p = 1; index_p < p.size(); index_p++) {
          new_p.add(p.get(index_p));
        }

        recursiveSeatPerson(combination, new_p, new_s);

      }
    } else {
      System.out.print(c + p.get(0)+s.get(0) + " ");
      System.out.println();
    }
  }

这是我的测试。

List<String> persons = Arrays.asList("P1", "P2", "P3");
List<String> seats = Arrays.asList("Sa", "Sb", "Sc");
recursiveSeatPerson("", persons, seats);

这是我的结果：

P1Sa, P2Sa, P1Sa, P2Sa, P1Sa, P3Sa 
P2Sa, P1Sa, P2Sa, P1Sa, P3Sa 
P1Sb, P2Sb, P1Sb, P2Sb, P1Sb, P3Sb 
P2Sb, P1Sb, P2Sb, P1Sb, P3Sb 
P1Sc, P2Sc, P1Sc, P2Sc, P1Sc, P3Sc 
P2Sc, P1Sc, P2Sc, P1Sc, P3Sc

现在在这一行中发送类似空字符串的参数：

recursiveSeatPerson("", new_p, new_s);

这是糟糕的结果（又一次）。

P1Sa, P2Sa, P3Sa 
P2Sa, P3Sa 
P1Sb, P2Sb, P3Sb 
P2Sb, P3Sb 
P1Sc, P2Sc, P3Sc 
P2Sc, P3Sc

如何解决我的代码？

Answer 1

工作代码：

private void recursiveSeatPerson(String snippet, List<String> p, List<String> s) {
  if (p.size() > 1) {
    for (int i = 0; i < s.size(); i++) {
      String combination = snippet + p.get(0) + s.get(i) + ", ";

      List<String> new_s = new ArrayList<>();
      for (int index_s = 0; index_s < s.size(); index_s++) {
        if (index_s != i) {
          new_s.add(s.get(index_s));
        }
      }
      List<String> new_p = new ArrayList<>();
      for (int index_p = 1; index_p < p.size(); index_p++) {
        new_p.add(p.get(index_p));
      }
      recursiveSeatPerson(combination, new_p, new_s);
    }
  } else {
    System.out.println(snippet + p.get(0)+s.get(0) + " ");
  }
}

使用 4 长度数组进行测试。

List<String> persons = Arrays.asList("P1", "P2", "P3", "P4");
List<String> seats = Arrays.asList("Sa", "Sb", "Sc", "Sd");
recursiveSeatPerson("", persons, seats);

检查输出：

P1Sa, P2Sb, P3Sc, P4Sd 
P1Sa, P2Sb, P3Sd, P4Sc 
P1Sa, P2Sc, P3Sb, P4Sd 
P1Sa, P2Sc, P3Sd, P4Sb 
P1Sa, P2Sd, P3Sb, P4Sc 
P1Sa, P2Sd, P3Sc, P4Sb 
P1Sb, P2Sa, P3Sc, P4Sd 
P1Sb, P2Sa, P3Sd, P4Sc 
P1Sb, P2Sc, P3Sa, P4Sd 
P1Sb, P2Sc, P3Sd, P4Sa 
P1Sb, P2Sd, P3Sa, P4Sc 
P1Sb, P2Sd, P3Sc, P4Sa 
P1Sc, P2Sa, P3Sb, P4Sd 
P1Sc, P2Sa, P3Sd, P4Sb 
P1Sc, P2Sb, P3Sa, P4Sd 
P1Sc, P2Sb, P3Sd, P4Sa 
P1Sc, P2Sd, P3Sa, P4Sb 
P1Sc, P2Sd, P3Sb, P4Sa 
P1Sd, P2Sa, P3Sb, P4Sc 
P1Sd, P2Sa, P3Sc, P4Sb 
P1Sd, P2Sb, P3Sa, P4Sc 
P1Sd, P2Sb, P3Sc, P4Sa 
P1Sd, P2Sc, P3Sa, P4Sb 
P1Sd, P2Sc, P3Sb, P4Sa

两个数组的递归组合项（非空或重复），使用 Java

Recursive Combinations Items of Two Arrays (not null or repeated), using Java

java

algorithm

recursion

combinatorics