July 30th, 2003, 02:54 PM

Finding all possible combos?
Hi group,
What I want to do is figure out the formula needed to output all possible combonations of an inputted string. For example:
Original string: 12345
Thus, I want to come up with a way to display all combonations of those five numbers (12354, 12534, 15234, 51234, etc..) without ever repeating the same combonation or having the same number twice in any new combonation. I have really thought hard on this for the past few weeks, but haven't yet found a solution that works. It seems like the solution isn't that hard to figure out, but I just can't get it right. If anyone can just give me the general idea on what to do (For...Loops, variable increments, etc.) I'd greatly appreciate it!
July 30th, 2003, 04:07 PM

This is called "permutation", iirc it is a *very* simple recursive algorithm and you should find a lot about it on google.
The general idea is to use a recursive function and make it run only over half of the possible results. The "towers of hanoi" problem iirc resolves to the same algorithm.
hth,
M.
July 30th, 2003, 05:49 PM

Off the top of my head:
Code:
pseudo code:
list lst
int pos
for(pos=0 to length(lst)){
doit(lst,pos)
)
function doit(lst,pos){
list sublist
int subpos
if(length(lst)==1){
print lst[0]
} else {
sublist=lstchar@(pos)
for(subpos=0 to length(sublist)){
print lst[pos]
doit(sublist,subpos)
}
}
}
August 4th, 2003, 01:21 AM

Ever heard of a factorial?
All you have to do is multiply the number of things being arranged (say 5) times the number  1 times the number  2 times the number  3. So it would be (in the case of there being 5 things being arranged) 5*4*3*2 (*1, but it makes no difference). There is a factorial built into many programming languages. In some, you can just say "m = 5!" for "m = 5*4*3*2*1" But you can always use a loop. Note: It may be easier, conceptually, if you use 1*2*3*4*5 because you get to do it "forwards."
August 4th, 2003, 01:25 AM

Oops. I thought you meant you needed to know the *number* of possible combinations.