# Generating Unique Combinations from a list of possible repeated characters

I am looking to generate combinations from a list of elements. Right now i am using a approach of generating power set. For example to generate combinations from {a,b,c}, i will enumerate 001,010,100 ,101 etc...and take the element for which the corresponding binary index is set to 1. But the problem comes when there are repeated characters in the list Say {a,a,b}. the above approach would give a,a,b,ab,ba,aa,aab. where as i would like to see only a,b,ab,aa,aab.

I was thinking of writing some binary mask to eliminate repeated strings but was not succesfull. Any thoughts on how to generate unique combinations ?

-
Model your solution on expanding the product $(1+a+a^2)(1+b)$. – Andy B Oct 4 '10 at 20:23
Instead of generating a binary string, why not generate a string $s_1,\ldots,\s_k$ in which $0 \leq s_i < n_i$ for each $i$? Set $n_i$ to be the number of instances of character $i$ in the multiset. – Andrew D. King Oct 6 '10 at 19:24

-
Thanks.It also should be there.I edited the question – user9792 Oct 4 '10 at 21:09

If you want something faster than filtering out repeats from the powerset then you can use


from itertools import product
from collections import Counter
print [''.join(x) for x in product(*[[k*i for i in range(v+1)] for k, v in Counter('aab').items()])][1:]

-

Suppose that your list contains $k$ distinct characters and the $i^{th}$ character appears $n_i$ times, for $1 \leq i \leq k$. Then, each combination corresponds to a vector of integers $(x_1, x_2, \ldots, x_k)$ where $0 \leq x_i \leq n_i$.

-