#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    1
    Rep Power
    0

    Question 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. #2
  3. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep 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.
  4. #3
  5. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    13
    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)
    		}
    	}
    }
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    27
    Rep 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."
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    27
    Rep Power
    0
    Oops. I thought you meant you needed to know the *number* of possible combinations.

IMN logo majestic logo threadwatch logo seochat tools logo