The
Problem
On several programs I've worked on I needed to know all possible arrangements of a
given number of objects.
Example: (4 objects)
Number of possibilities = 4! or 1*2*3*4 = 24
I was able to write them all down (1234, 1342, 4321, and so on) but I wanted an algorithm
to generate all of them.
The challenge is to write a program to generate all possible arrangements of 4 objects or
any number of objects.
Can you do this? I would like to see if any one else could come up with a different
solution than I did. I found this problem to be a quite a challenge, it took me
hours to figure it out.
The
Solution
<script>
var a,b,c; //Base x! special count
s = new Array(3); //Original object array 1234
s[3]=1; s[2]=2; s[1]=3; s[0]=4; //Set original (seed)
m = new Array(3); //Working object array
for (a=0; a<=3; a++) //Base 3!
{for (b=0; b<=2; b++) //Base 2!
{for (c=0; c<=1; c++) //Base
1!
{
document.writeln(a+""+b+""+c+" "); //Display
count
m[0]=s[0]; m[1]=s[1];
m[2]=s[2]; m[3]=s[3]; // Get original sequence
t=m[3]; m[3]=m[3-a];
m[3-a]=t; //Swap 4th Digit
t=m[2]; m[2]=m[2-b];
m[2-b]=t; //Swap 3rd Digit
t=m[1]; m[1]=m[1-c];
m[1-c]=t; //Swap 2nd Digit
//1st Digit will always swap with self and is constant and doesn't matter
document.writeln(m[3]+""+m[2]+""+m[1]+""+m[0]+"<br>");
//Display sequence
}
}
}
</script>
Run
| Run Output |
Decimal count |
Factorial count |
4 Selected |
000 1234
001 1243
010 1324
011 1342
020 1432
021 1423
100 2134
101 2143
110 2314
111 2341
120 2431
121 2413
200 3214
201 3241
210 3124
211 3142
220 3412
221 3421
300 4231
301 4213
310 4321
311 4312
320 4132
321 4123
|
Base 10 |
Base X! |
Objects |
| 0 |
000 |
1 2 3 4 |
| 1 |
001 |
1 2 4 3 |
| 2 |
010 |
1 3 2 4 |
| 3 |
011 |
1 3 4 2 |
| 4 |
020 |
1 4 3 2 |
| 5 |
021 |
1 4 2 3 |
| 6 |
100 |
2 1 3 4 |
| 7 |
101 |
2 1 4 3 |
| 8 |
110 |
2 3 1 4 |
| 9 |
111 |
2 3 4 1 |
| 10 |
120 |
2 4 3 1 |
| 11 |
121 |
2 4 1 3 |
| 12 |
200 |
3 2 1 4 |
| 13 |
201 |
3 2 4 1 |
| 14 |
210 |
3 1 2 4 |
| 15 |
211 |
3 1 4 2 |
| 16 |
220 |
3 4 1 2 |
| 17 |
221 |
3 4 2 1 |
| 18 |
300 |
4 2 3 1 |
| 19 |
301 |
4 2 1 3 |
| 20 |
310 |
4 3 2 1 |
| 21 |
311 |
4 3 1 2 |
| 22 |
320 |
4 1 3 2 |
| 23 |
321 |
4 1 2 3 |
The
Explanation
Understanding the Base x! special count.
First lets review Base 2:
|
|
To convert binary to decimal:
1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 13 |
Now lets look at Base x!: (remember 5! = 1*2*3*4*5 = 120)
|
|
To convert factorial to decimal:
2*3! + 2*2! + 1*1! + x*0! or
2*6 + 2*2 + 1*1 + x*0 = 17 |
Have you ever seen this type of counting before? (see above
for sequence.)
The LSD is not only the Least Significant Digit, but is also insignificant.
Applying the factorial counter
to the sequence.
For each count, use the same seed sequence (1234), or any starting sequence.
The count tells you how to transform the seed value to the new sequence. Digits(1-4)
of the count corresponds to digits(1-4) of the seed. The value of the count digit tells
you witch digit to the right of the corresponding digit in the seed to swap it with. Start
with digit 1 and the seed value, apply the transformation, use the newly generated number
as the next seed value and do the same with digit 2, and so on.
Example #1 (2 2 1 x) |
| Digit # > |
d1 |
d2 |
d3 |
d4 |
start with d1, d2, d3... |
| X! count > |
2 |
2 |
1 |
x |
d1 (2) of the
count applies to d1 of the seed (1). |
| Seed > |
1 |
2 |
3 |
4 |
The value in d1 (2) tells you how many digits to the right to swap with, {d[1]<=>d[1+2]} |
| 2's (result) |
3 |
2 |
1 |
4 |
New seed value. |
| next d2 |
3 |
2 |
1 |
4 |
The value in d2 (2) tells you how many digits to the right to swap with, {d[2]<=>d[2+2]} |
| 2's (result) |
3 |
4 |
1 |
2 |
New seed value. |
| next d3 |
3 |
4 |
1 |
2 |
The value in d3 (1) tells you how many digits to the right to swap with, {d[3]<=>d[3+1]} |
| 1's (result) |
3 |
4 |
2 |
1 |
New seed value. |
| results |
3 |
4 |
2 |
1 |
End result! |
x |
3 |
4 |
2 |
1 |
Do nothing, insignificant, stays constant.... |
Example 2 (301x)
Start with the seed (1234)
d1 of the count =3: swap d1 of seed, with the 3rd to the right of d1 (the 4).
Transformation now is (4231)
d2 of the count =0: swap d1 with d(1+0), swap with self or do nothing.
Transformation now is (4231)
d3 =1: swap d3 with d4.
Transformation now is (4213)
(4213) Done.
There's more:
see above for converting
factorial to decimal.
The divide by method : Start at the right most
significant digit.
| Decimal |
Factorial |
- |
| - |
|
- |
| 21 |
|
[21 / (base+1)] = [21 / 2] = 10.5: Using the fractional part to
generate the last digit: .5 * (base +1) = .5 * 2 = 1 |
| 10 |
|
Using the whole part: 10 / 3 = 3.333 : .333 * 3 = 1 |
| 0 |
|
3 / 4
= 0.75 : .75 * 4 =
3 : The whole
part < 1 then STOP. |
I had figured this out, but I think I'll leave it to you to figure out.
This will test your understanding, it's also another challenge. I don't know why you might
want to do this though.
<script>
for (m=0; m<24; m++) //Decimal count (0-23)
{s = new Array(1,2,3,4); mt=m;
for (a=1; a<=3; a++)
{
t=mt/(a+1); mt=Math.floor(t); f=Math.round((t-mt)*(a+1));
t2=s[a]; s[a]=s[a-f]; s[a-f]=t2;
}
document.write(""+s[0]+""+s[1]+""+s[2]+""+s[3]+"<br>");
//Sequence output
}
</script>
Why would you need to do this.
1) Game piece generation:
I resolved this problem after playing "The crazy turtle game".
Their version of the game only has one puzzle, so once you solved it you knew how
to do it again. I wanted to have it re-generate a different puzzle each time.
The game consisted of a 3 * 3 game grid, and 9 pieces. Each piece
has 4 half turtles each with a different color. The object is to match all the turtles and
colors up by rotating them and placing them anywhere on the board.
There are 24 possible different pieces, and only nine are needed for each
puzzle. What I needed was all 24 possible arrangements.
2) Brute force solving:
When I was solving "word math puzzels" there were a few I
couldn't solve, so I thought I would write a program to solve them.
Word math problems, are long division problems, where all the numbers are
replaced with letters. The object was to find what numbers substituted the letters.
I used brute force to try all possible 10 digit combinations to see which
one worked.
Actually, I solved for some of the numbers, so I only had to try all
possible arrangements of 5-7 digits.
3) puzzle help:
When solving "Cross sums" puzzles, in many cases there are only
one set of numbers that can fit, but they can be arranged in any order. What I needed was
a list of all possible arrangements, so I could cross them off when I found that, that
arrangement couldn't work.
Cross sums is a common puzzle found in puzzle books like "Dell Pencil
Puzzles".
|