Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
2  
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

3 Answers 3

...what about aa

share|improve this answer
    
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:]
share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.