Finding all possible combos?

Dev Shed Forums Sponsor:

July 30th, 2003, 02: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!

July 30th, 2003, 04:07 PM

M.Hirsch

Contributing User

Dev Shed God 1st Plane (5500 - 5999 posts)

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: 189

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.

July 30th, 2003, 05: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: 11

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)
		}
	}
}

August 4th, 2003, 01: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."

August 4th, 2003, 01:25 AM