Page 1 of 1
Posted: Mon Feb 10, 2003 4:01 pm
by 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
Posted: Tue Feb 11, 2003 8:47 am
by 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
Posted: Tue Feb 11, 2003 9:38 am
by 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.
Posted: Tue Feb 11, 2003 10:15 am
by 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
Posted: Wed Mar 26, 2003 5:29 am
by Abednego
Look here:
http://ttc.stefan-pochmann.de/
under Tutorials->Sets,Subsets
Posted: Wed Mar 26, 2003 3:00 pm
by 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.
Generating all permutations
Posted: Thu Jun 12, 2003 2:55 pm
by 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
Posted: Sat Jun 14, 2003 1:35 pm
by anupam
hello all,
i want to know abt pochmen.
he was a great helper.
can any1 give me info of pochmen.
--
Posted: Sat Jun 14, 2003 7:40 pm
by Moni
Yeah! Hope soon he will come back from his TOP CODER journey
