有没有有效的算法可以返回所有不同的组合？

Question

编辑：我的意思是组合而不是排列

是否有有效算法可以返回给定数组中的所有不同排列？ [“A”，“B”，“C”，“D”，“E”，“F”，“G”，“H”，“I”，“J”，“K”，...]

例如：AB,AC,AD,..,DE,..,HI,..,ABC,ABD,...,DEF,..,CDEFG,...,ABCDEFGHIJK,....

我发现了一些算法，但它们返回所有排列，而不是不同的排列。 不同我的意思是：

1. AB 和 BA 是相同的排列

2. DEF & FED & EFD & DFE 是相同的排列，

Answer 1

我能想到的最好的就是二进制计数器：

 A B C
-------
 0 0 0 | Empty Set
 0 0 1 | C
 0 1 0 | B
 0 1 1 | BC
 1 0 0 | A
 1 0 1 | AC
 1 1 0 | AB
 1 1 1 | ABC

Answer 2

任何给定的项目要么在组合中，要么不在组合中。为每个项目考虑一个布尔标志，说明它是否在组合中。如果您检查了布尔标志的每个可能的值列表，您就已经检查了每种组合。

布尔值列表也称为二进制整数。

如果您有商品 A-K，则您有 11 件商品。因此，检查所有可能的 11 位数字。在爪哇：

for (int flags = 0; flags < (1 << 11); ++flags) {
    int x = indexOfSomeItemFromZeroToTen();
    boolean isInCombination = ((i >> x) & 1) == 1;
}

如果您想跳过空组合，请从 1 而不是 0 开始。

Answer 3

1. 正如评论所指出的，您希望枚举所有子集，而不是排列。

2. 最简单的方法是使用二进制计数器。例如，假设你有 n 个元素，那么这样的东西在 C 中就可以工作：

代码：

for(int i=0; i<(1<<n); ++i)  {
   //Bits of i represent subset, eg. element k is contained in subset if i&(1<<k) is set.
}

希望这能帮助解答您的问题

Answer 4

这些不是排列。 ABC的

排列

是

{ABC, ACB, BCA, BAC, CAB, CBA}

。您有兴趣找到 {A,B,C, ..., K, ...} 的 所有不同子集（也称为 幂集）。这很容易做到：每个元素都可以包含或排除。这是一个递归算法：

power_set(U) =
   if U == {} then
      {{}};     
   else 
      union( { first(U), power_set(tail(U)) },  // include
             { power_set(tail(U)) }             // exclude
           );

Answer 5

这是我编写的一些 Ruby 代码，用于迭代数组中的每个组合。

def _pbNextComb(comb,length) # :nodoc:
 i=comb.length-1
 begin
  valid=true
  for j in i...comb.length
   if j==i
    comb[j]+=1
   else
    comb[j]=comb[i]+(j-i)
   end
   if comb[j]>=length
    valid=false
    break
   end
  end
  return true if valid
  i-=1
 end while i>=0
 return false
end

#
# Iterates through the array and yields each
# combination of _num_ elements in the array
#
# Takes an array and the number of elemens
 # in each combination
def pbEachCombination(array,num) 
 return if array.length<num || num<=0
 if array.length==num
  yield array
  return
 elsif num==1
  for x in array
   yield [x]
  end
  return
 end
 currentComb=[]
 arr=[]
 for i in 0...num
  currentComb[i]=i
 end
 begin
  for i in 0...num
   arr[i]=array[currentComb[i]]
  end
  yield arr
 end while _pbNextComb(currentComb,array.length)
end