从 1 个列表生成 2 个组合的算法

Question

我需要一个算法来生成 2 个列表，其中 3 个字符取自 6 个字符的列表。例如，我有一个包含 [a,b,c,d,e,f] 的数组，我想创建 [a,b,c][d,e,f] 这样的组合。

我需要得到 2×3 个字符的所有可能组合。

约束

两个组合不能相同。我的意思是我不能以不同的顺序将 2 次相同的 3 个字符放在一起。因此，如果 [a,b,c][d,e,f] 已经生成，我不能将 [b,a,c][f,d,e] 作为另一种可能性或 [f,d,e][b,a,c].

理想情况下，如果算法在 javascript 中，但我愿意接受任何其他建议（我可以阅读代码，即使我不知道我最有可能使用的语言能够用我不知道的语言理解算法）。我看过很多关于排列和组合的帖子和问题，但 none 似乎是我正在寻找的东西，我似乎无法弄清楚如何修改它们以适应我正在寻找的东西对于.

Answer 1

尝试结合使用树和 queue/stack 数据结构来实现这种行为。算法应该很简单相关树遍历看起来像。

Answer 2

给定包含元素 {1, …, 6} 的输入集，您需要 1. 生成 {2, …, 6} 和 的所有不同的 3 子集2. 计算每个子集与输入集的交集（余数）：

function* subsets(input, length, start = 0) {
  if (start >= input.length || length < 1) yield [new Set(), new Set(input)];
  else {
    for (let i = start; i <= input.length - length; ++i) {
      let first = input[i];
      for ([subsubset, remainder] of subsets(input, length - 1, i + 1)) {
        subsubset.add(first);
        remainder.delete(first);
        yield [subsubset, remainder];
      }
    }
  }
}

let input = ['a', 'b', 'c', 'd', 'e', 'f'];

for ([subset, remainder] of subsets(input, 3, 1)) {
  console.log([...subset].join(''), [...remainder].join(''));
}

这与 . See also 对为什么我们不将第一个元素包含在我们的 3 子集中的详尽解释所概述的算法非常相似（为了防止重复，它包含在其余部分中！ ).

如果您的输入元素不是唯一的，您将需要运行上述算法对输入的索引而不是其值进行计算。

如果您的输入大小大于 6，您也需要与余数的所有子集合并：

for ([subset, remainder] of subsets(input, 3, 1)) {
  for ([remainder_subset, _] of subsets([...remainder], 3)) {
    console.log([...subset], [...remainder_subset]);
  }
}

Answer 3

我能想到的暴力破解方法：-

第一个位置可以有 6 个选项中的任何一个。第二个位置可以有五分之一第三可以有四分之一。

其余 3 个将进入另一个列表。所以基本上需要做的是：-

继续生成所有 3 种尺寸组合并将它们放入哈希图中。在生成新组合时检查它是否存在于地图中。如果是，则跳过它，否则将其添加到地图中。有效的方法可能是存储组合的排序顺序。

希望对您有所帮助！！

Answer 4

很简单：

迭代 {2, …, 6} 的所有 2-子集，例如使用回溯。
对于每个子集 S，考虑 H1 = S ⋃ {1}、H2 = {1, …, 6} ∖ H1
当前组合由 H1 中的索引给出的 A 中的项目和 H2

A

由于这强制执行 1 ∈ H1，您将不会获得像 [a,b,c][d,e,f]、[d,e,f][a,b,c].

这样的重复

由于集合没有顺序，您不会获得像 [a,b,c][d,e,f]、[b,a,c][f,d,e].

这样的重复

Answer 5

避免[a,b,c] ⇆ [a,c,b] 重复，从 "a" 到 "d" 中选择第一个玩家，在第一个玩家之后的第二个玩家最多 "e"，在第二个玩家之后的第三个玩家最多 "f"。

避免[a,b,c][d,e,f] ⇆ [d,e,f][a,b,c] 重复，让玩家 "a" 在第一队。

这是执行此操作的最简单代码：（它为一个团队挑选人员；第二个团队显然由其他 3 人组成）

function distribute(n) {
    for (var i = 1; i < 5; i++) {
        for (var j = i + 1; j < 6; j++) {
            document.write("team 1: " + n[0] + ", " + n[i] + ", " + n[j] + "<br>");
        }
    }
}
distribute(["a","b","c","d","e","f"]);

Answer 6

这个问题的主要观察点是：我们不需要构建第二个三项列表，一旦我们构建了第一个三项列表，第二个列表只是第一个列表的补充.

示例：

假设我们select 3 项为[a , b , c]，第二个列表简单地得到为

[a , b , c , d , e , f] - [a , b , c] = [d , e , f]

所以我们将只关注第一个列表(list 1)。

让我们关注任何一个元素，比如说a（任意取）。我们观察到：

每个可能的组合总是将 a 作为两个列表中的某个列表的成员，并且以包含 a 的那个为准，我们称之为列表 1.让我们 select 其他成员 list 1.

我们有 select 第一个成员。第二个成员可以从 [b , c , d , e , f] 中 select 编辑。

在我们算法的第一次迭代中，我们将 select 第二个成员设为 b。第三个成员可以有四个可能性。这意味着我们必须 select 来自 [c , d , e , f] 的一个元素。一旦我们 select 第三个成员，我们的 list 1 就完成了，list 2 也完成了。当第三个成员已考虑所有 4 种可能性时，第一次迭代完成。

在我们算法的第二次迭代中，我们将 select 第二个成员设为 c。现在第三个成员只能有3种可能，而且NOT4，因为我们已经考虑了b。三种可能性将是 [d , e , f]。一旦我们 select 第三个成员，我们的 list 1 就完成了，list 2 也完成了。当第三个成员已考虑所有 3 种可能性时，第二次迭代完成。

类似地，在第三次迭代中，我们的第二个成员将是 d，而我们将有 2 个可能的第三个成员 [e , f]。

同样，在第四次迭代中，我们的第二个成员将是e，而对于第三个成员，我们将只有一种可能性，即f。

注意

我们不必担心我们的算法会有多少次迭代，我们算法的终止条件将是可能组合的总数，即6choose3/2 = 10.

使用的数据结构

我们会不会使用一个长度为6位的数组arr，对于list 1的每个组合，我们将1放在相应的位置。因为它会被初始化为0，所以每一个0，就代表list 2.

的成员

意思是list 1 = [a , b , c]，那么arr = [1 , 1 , 1 , 0 , 0 , 0]

我们算法的伪代码如下：

Initialize an array of character of length 6 namely set = [a , b , c , d , e , f]

Initialize an array of integer(or boolean to save space cause we will be storing only 0 
and 1) of length 6 namely arr,initialized to 0.

int x = 10, total = 0,i = 1.
arr[0] = 1// because element a belongs to list 1

while(total < x)
{
 arr[i] = 1

 for(j = i + 1 to 5)
 {
  arr[j] = 1
  list 1 is made of all elements set[k] such that arr[k] = 1
  list 2 is made of all elements set[k] such that arr[k] = 0
  arr[j] = 0
 }

 total = total + 5 - i 
 arr[i] = 0
 i = i + 1
}

伪代码易于理解，应该很容易 code.Take 作为练习。

从 1 个列表生成 2 个组合的算法

Algorithm to generate 2 combinations from 1 list

javascript

arrays

algorithm

combinatorics