Есть ли эффективный алгоритм, который будет возвращать все различные комбинации?

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-битным числам. В Java:

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

Вот некоторый код на 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

Answer 5

Это не перестановки. перестановки из 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
           );