Is there effective algorithm that will return all different combination?

EDITED: I meant COMBINATION and not PERMUTATIONS

Is there effective algorithm that will return all different permutations from the given array? ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", ...]

e.g.: AB,AC,AD,..,DE,..,HI,..,ABC,ABD,...,DEF,..,CDEFG,...,ABCDEFGHIJK,....

I found some algorithms, but they return ALL permutation and not different ones. By different I mean that:

1. A开发者_运维问答B & BA are the same permutations

2. DEF & FED & EFD & DFE are the same permutations,

---

The best I can think is sort of a binary counter:

 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

---

Any given item is either in the combination or not. Think of a boolean flag for each item, saying whether it's in the combination. If you go through every possible list of values of the boolean flags, you've gone through every combination.

Lists of boolean values are also called binary integers.

If you have items A-K, you have 11 items. So, go through all the possible 11-bit numbers. In Java:

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

Start at 1 instead of 0 if you want to skip the empty combination.

---

1. As pointed out by the comments, you are looking to enumerate all subsets, not permutations.

2. The easiest way to do this is to use a binary counter. For example, suppose you have n-elements, then something like this would work in C:

code:

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.
}

I hope this helps answer your question

---

Here is some Ruby code I've written and had for a while now that iterates through each combination in an array.

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

---

These are not permutations. The permutations of ABC are {ABC, ACB, BCA, BAC, CAB, CBA}. You are interested in finding all distinct subsets (otherwise known as the power set) of {A,B,C, ..., K, ...}. This is easy to do: each element can be either included or excluded. Here's a recursive algorithm:

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