0
$\begingroup$

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 ?

$\endgroup$
2
  • 2
    $\begingroup$ Model your solution on expanding the product $(1+a+a^2)(1+b)$. $\endgroup$ – Andy B Oct 4 '10 at 20:23
  • $\begingroup$ 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. $\endgroup$ – Andrew D. King Oct 6 '10 at 19:24
1
$\begingroup$

...what about aa

$\endgroup$
0
1
$\begingroup$

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:]
$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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