Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
July 30th, 2003, 03:54 PM
 milzzy
Junior Member

Join Date: Jul 2003
Posts: 1
Time spent in forums: < 1 sec
Reputation Power: 0
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!

#2
July 30th, 2003, 05:07 PM
 M.Hirsch
Contributing User

Join Date: Oct 2000
Location: Back in the real world.
Posts: 5,966
Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 190
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.
__________________
--
Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.

#3
July 30th, 2003, 06:49 PM
 dog135
Doggie

Join Date: Jul 2003
Location: Seattle, WA
Posts: 751
Time spent in forums: 10 h 38 m 25 sec
Reputation Power: 12
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=lst-char@(pos)
for(subpos=0 to length(sublist)){
print lst[pos]
doit(sublist,subpos)
}
}
}```

#4
August 4th, 2003, 02:21 AM
 Pi Man
Registered User

Join Date: Aug 2003
Posts: 27
Time spent in forums: 37 m 10 sec
Reputation Power: 0
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."

#5
August 4th, 2003, 02:25 AM
 Pi Man
Registered User

Join Date: Aug 2003
Posts: 27
Time spent in forums: 37 m 10 sec
Reputation Power: 0
Oops. I thought you meant you needed to know the *number* of possible combinations.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Finding all possible combos?