How to Generate Distinct Combinations

[Dominik Michniewski]

if you use C++,try to use function next_perm() (or something near that name - I don't remember it correct) ....

If you want try other way - read about permutations from Knuth .... in this book is given algorithm , which do this ) but be very carefull - generating all distinct permutations can take a very very long time .... when I write such function long time ago, I found that for 11 different characters all permutations my computer compute 1 hour (with printing to screen) ....

Best luck
Dominik Michniewski

[Dominik Michniewski]

If you want only combinations like:
AAABC, AAACB, BAAAC, CAAAB, BCAAA, CBAAA and nothing other - try to permute unique symbols, and repetitions add only for output - in this case permute only string ABC )

I don't know - it's your problem ?
If not, try to tell me more about it ))

Dominik

[asar786]

let say i have symbols
A,B,C,D,E,F (N=6)
i hav to find unique sets of order K. such that
repeatation of symbol is also required
but a set in whole can not be repeated by means of its permutation
let say K=3

for AAA...AFF

AAA ACA* AEA*
AAB ACB* AEB*
AAC ACC AEC*
AAD ACD AED*
AAE ACE AEE
AAF ACF AEF
ABA* ADA* AFA*
ABB ADB* AFB*
ABC ADC* AFC*
ABD ADD AFD*
ABE ADE AFE*
ABF ADF AFF

the starred entries are not required because they r repeating

ABA is same as AAB,BAA,

how to drop those.

[Dominik Michniewski]

try to generate all possible permutations, which have that property that val(a_i) is less or equal than val(a_j) foreach i,j

try to use BFS
in first step insert to queue letters A,B,C,D,E,F ....

qlen - length of queue
qact - act element in queue

Code: Select all

MAX = 6; /* size of {A,B,C,D,E,F} set */
while(qact < qlen)
{
   q = queue[qlen];
   if(LENGTH(q) >= K) break; /* in positions K..qlen are permutations ... */
   for(i=0;i<MAX;i++) if(UNIQUE_IN_QUEUE(q + set(i))
   {
      INSERT_TO_QUEUE(q + set(i));
      qlen++;
   }
   qact++;
}

UNIQUE_IN_QUEUE could be realized as you wish - linear search, binary search, lookup table
INSERT_TO_QUEUE could be realized the same - it's very important to insert data to queue by it's length....

I think that time complexity is O(N^2) where N is number of combinations ...

I hope, that should be work

Regards
Dominik

[Abednego]

Look here:
http://ttc.stefan-pochmann.de/
under Tutorials->Sets,Subsets

[junjieliang]

Maybe the way he used "val(a_i) <= val(a_j) for each i,j" looks intimidating, but in short he's saying that your sequences should be in non-descending order. Therefore, print ABC only and ignore that other 5 since they are not in non-descending order. To make sure you don't get AAAB 2 or 3 times, you would have to keep track to make sure you don't permute the same character twice.

I think your problem can be solved by recursion... if I'm free I'll send you a code through PM.

[kpras]

Hi
This can be done using cyclisation and recursion ; Lets take a word
say code. You think of this word as placed as a circular array,
key for recursion is that all the words starting with c are : c added
in the start to all the permutations of the string "ode". similarly for
"ode" now. ...
Going back to stack of recusion all words starting wih o are ...
If some letters of alphabet are repeated in the word ,then we
end up getting repetitions think a bit how to handle it
bye

[anupam]

hello all,
i want to know abt pochmen.
he was a great helper.
can any1 give me info of pochmen.
--

[Moni]

Yeah! Hope soon he will come back from his TOP CODER journey