Method to generate every possible combination of a given # of characters...

[Superwormy]

Say you're given 5 characters, say they are:

a, d, i, k, z


I need a methodical way to generate every possible unique string using those characters, ie:

adikz
adkzi
akzid


Etc. etc. etc. theres probably lots of them... I can't think of an easy way to do it where I'm not just randomly shuffling an array of letters to come up with combinations... I need to be able to get EVERY combination of letters, it can't be left up to chance.

I need to eventuallyt convert this to PHP and C... but I won't worry about that for now, just looking for a good general method to do this... am I missing something or is this a harder problem than it seems at first?

 

[notfred]

keep 5 counters, when one fills up reset it,move left and increment. Think of an odometer in a car.

 

[chiwawa626]

Heh if this is your homework its nice that your asking for help, not outright trying to buy the program of people 🙂

 

[dighn]

edit
completely misread it

 

[human2k]

one word: scrabble.

 

[Superwormy]

Actually human2k, you're absolutely right 🙂

It's actually a project that somebody else was talking about that I overheard... and now its pissing me off because I can't find out how to do it quickly and efficiently! The project is to get stats about the first move of a scrabble game, I can get everythign EXCEPT for this little part!

 

[ViRGE]

Embeded loops. The inner-most loop is the last letter, then as you work outwards, it's going left, changing letters as it increments.

 

[Savarak]

Originally posted by: Superwormy
generate every possible unique string using those characters

the term you want is PERMUTATION

 

[her209]

Originally posted by: Savarak

Originally posted by: Superwormy
generate every possible unique string using those characters

the term you want is PERMUTATION

EDIT: You also have to think about the possiblity of being given the same letter more than once, say for example, P E E. You will have to figure out some way to eliminate doubles.

 

[lukatmyshu]

Think of it recursively ... you have the letters a,b,c,d and e and a blank-character. So if you fix the first character you then have 6 possible choices for the 2nd character. You can imagine a 6 nested loops .... if you have to do this recursively say you have a global array of all possible inputs, and the function is passed in the maximum number of characters. You have a helper function that takes as it's arguments the number of letters left and the permuatation so far. The function iterates through your global array and each time takes one of the characters and calls itself with the permuatation + the selected character, and the index is decremented. When you reach 1 instead of recursing just print it out (or store it in another global array or whatever)

 

[SuepaFly]

I think theres a function on the calculator, if I remember correctly from stats. One means without repeating order (like adikz = zkida) while the other means all possible combos. I can remember the function right now though, something with an rcn or something...? I may be wrong, but I remember doing problems like this before and there is a formula

 

[wfbberzerker]

Originally posted by: SuepaFly
I think theres a function on the calculator, if I remember correctly from stats. One means without repeating order (like adikz = zkida) while the other means all possible combos. I can remember the function right now though, something with an rcn or something...? I may be wrong, but I remember doing problems like this before and there is a formula

for permutations: nPr
for combinations: nCr
they are under the MATH -> PRB menu (on the ti-83, at least)

 

[her209]

nm

 

[SuepaFly]

Originally posted by: wfbberzerker

Originally posted by: SuepaFly
I think theres a function on the calculator, if I remember correctly from stats. One means without repeating order (like adikz = zkida) while the other means all possible combos. I can remember the function right now though, something with an rcn or something...? I may be wrong, but I remember doing problems like this before and there is a formula

for permutations: nPr
for combinations: nCr
they are under the MATH -> PRB menu (on the ti-83, at least)

Ah sweet, thats it, I switched the letters up a bit. Thats what a 6 figure education teaches you a year after graduation.

 

[glugglug]

1 char is obvious (has only 1 order)
2 chars can be either one first
3 chars what you do is this: for both orders that the last 2 chars can be in, insert the first char in all 3 possible positions (1st, middle, last)
4 chars you take all the possible orders the last 3 chars can be in, then insert 1st char into all 4 possible positions on each of those orders.
etc.

 

[Barnaby W. Füi]

It's alot easier to do if the number of letters is fixed. I'm workin on somethin (just for the hell of it, it may or may not be of use to you 🙂)

 

[dighn]

nm i completely misread the question

 

[her209]

A = {A,B,C,D,E,...}

|A| = number of elements in A

Main()
{
Array = {...}
String = ""
Count = 0
While the count <= SizeOf(Array)
{
Enumerate(Array)
Rotate(Array)
count = count+1
}

}

Enumerate(AnotherArray,String)
{
While(SizeOf(AnotherArray) > 0)
{
String = String + AnotherArray[0]
NewArray = AnotherArray - AnotherArray[0]
Enumerate(NewArray,String)
Rotate(AnotherArray)
}
Print String
}

Rotate(AnotherArray)
{
Shift all elements up one and move the front element to the back
}

==============================================

Confused yet?

 

[Barnaby W. Füi]

Cool, I was beginning to get frustrated, there are kids screaming outside my room and I'm most definitely not in an algorithmic mood :disgust:

 

[Noirish]

single array {a, b, c, d ,e}

embedded loop.

for (int i=0, i < 5, i++) {
for (int j=4, j > -1, j--) {
}
}

 

[her209]

Did you get what you were looking for?