Generating Unique Combinations from a list of possible repeated characters

Question

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,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 ?

Answer 1

Rather than generate bit vectors, you can generate vectors of positive integers of length equal to the number of distinct elements, subject to the restriction that each component can range from 0 up to the multiplicity of the corresponding element. In your example above, there are two distinct elements (a and b) with multilpicities 2 and 1, respectively. Therefore, you would get

a b
-------
0 1 --> b
1 0 --> a
1 1 --> ab
2 0 --> aa
2 1 --> aab