Home » Archimedes archive » Acorn User » AU 1997-10 A.adf » Extras » Apple][e/PD/BOB/ARMBOB/!ArmBob/progs/Permute
Apple][e/PD/BOB/ARMBOB/!ArmBob/progs/Permute
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » Archimedes archive » Acorn User » AU 1997-10 A.adf » Extras |
| Filename: | Apple][e/PD/BOB/ARMBOB/!ArmBob/progs/Permute |
| Read OK: | ✔ |
| File size: | 0669 bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
File contents
/* permutations GCW 11/01/95
This uses and displays the following algorithm for
running through permutations from 0 1 ... n to
n ... 1 0.
Step 1. Starting from the right hand end, find the
first element smaller than its right hand
neighbour - call it fred. Then find the
next largest number to the right of fred,
call it sam.
Step 2. Swap fred and sam.
Step 3. Reverse the list of numbers to the right
of fred's old position.
This program shows the intermediate steps, underlining
the pair (fred,sam).
*/
main()
{
do
{
print("Input a smallish number (2-7): ");
n = val(input());
}
until (n < 8 && n > 1);
v = newvector(n);
fact = 1;
for ( k = n; k > 0;)
{
fact *= k--;
v[k] = k;
}
print("> ");
display(v);
newline();
for (k = 1; k < fact; k++)
permute(v);
}
display(v)
{
local i,n;
n = sizeof(v);
for ( i = 0; i < n; i++)
print(v[i]," ");
}
newline()
{ print("\n"); }
permute(v)
{
local n,fred,sam;
n = sizeof(v);
sam = n-1;
fred = sam-1;
while (v[fred] > v[fred+1] && fred > 0) fred--;
while (v[sam] < v[fred] && sam > fred) sam--;
underline(fred,sam,n);
swap(v,fred,sam);
display(v);
reverse(v,fred+1);
print(" reverse\n> ");
display(v);
newline();
}
reverse(v,k)
{
local n,i,half,offset;
n = sizeof(v);
half = (n+k)/2;
offset = n+k-1;
for (i = k; i < half; i++)
swap(v,i,offset-i);
}
swap(v,i,j)
{
local w;
w = v[i];
v[i] = v[j];
v[j] = w;
}
underline(i,j,n)
{
local k;
print(" ");
for(k = 0; k < n; k++)
print(((k == i)||(k == j))?"^ ":" ");
print(" swap\n ");
}
00000000 2f 2a 20 70 65 72 6d 75 74 61 74 69 6f 6e 73 20 |/* permutations |
00000010 20 20 20 20 20 47 43 57 20 20 20 20 20 20 31 31 | GCW 11|
00000020 2f 30 31 2f 39 35 20 20 20 0a 0a 20 20 20 54 68 |/01/95 .. Th|
00000030 69 73 20 75 73 65 73 20 61 6e 64 20 64 69 73 70 |is uses and disp|
00000040 6c 61 79 73 20 74 68 65 20 66 6f 6c 6c 6f 77 69 |lays the followi|
00000050 6e 67 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f 72 |ng algorithm for|
00000060 0a 20 20 20 72 75 6e 6e 69 6e 67 20 74 68 72 6f |. running thro|
00000070 75 67 68 20 70 65 72 6d 75 74 61 74 69 6f 6e 73 |ugh permutations|
00000080 20 66 72 6f 6d 20 30 20 31 20 2e 2e 2e 20 6e 20 | from 0 1 ... n |
00000090 74 6f 0a 20 20 20 6e 20 2e 2e 2e 20 31 20 30 2e |to. n ... 1 0.|
000000a0 20 20 0a 20 20 20 53 74 65 70 20 31 2e 20 53 74 | . Step 1. St|
000000b0 61 72 74 69 6e 67 20 66 72 6f 6d 20 74 68 65 20 |arting from the |
000000c0 72 69 67 68 74 20 68 61 6e 64 20 65 6e 64 2c 20 |right hand end, |
000000d0 66 69 6e 64 20 74 68 65 0a 20 20 20 20 20 20 20 |find the. |
000000e0 20 20 20 20 66 69 72 73 74 20 65 6c 65 6d 65 6e | first elemen|
000000f0 74 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 20 69 |t smaller than i|
00000100 74 73 20 72 69 67 68 74 20 68 61 6e 64 20 0a 20 |ts right hand . |
00000110 20 20 20 20 20 20 20 20 20 20 6e 65 69 67 68 62 | neighb|
00000120 6f 75 72 20 2d 20 63 61 6c 6c 20 69 74 20 66 72 |our - call it fr|
00000130 65 64 2e 20 54 68 65 6e 20 66 69 6e 64 20 74 68 |ed. Then find th|
00000140 65 0a 20 20 20 20 20 20 20 20 20 20 20 6e 65 78 |e. nex|
00000150 74 20 6c 61 72 67 65 73 74 20 6e 75 6d 62 65 72 |t largest number|
00000160 20 74 6f 20 74 68 65 20 72 69 67 68 74 20 6f 66 | to the right of|
00000170 20 66 72 65 64 2c 0a 20 20 20 20 20 20 20 20 20 | fred,. |
00000180 20 20 63 61 6c 6c 20 69 74 20 73 61 6d 2e 0a 20 | call it sam.. |
00000190 20 20 53 74 65 70 20 32 2e 20 53 77 61 70 20 66 | Step 2. Swap f|
000001a0 72 65 64 20 61 6e 64 20 73 61 6d 2e 0a 20 20 20 |red and sam.. |
000001b0 53 74 65 70 20 33 2e 20 52 65 76 65 72 73 65 20 |Step 3. Reverse |
000001c0 74 68 65 20 6c 69 73 74 20 6f 66 20 6e 75 6d 62 |the list of numb|
000001d0 65 72 73 20 74 6f 20 74 68 65 20 72 69 67 68 74 |ers to the right|
000001e0 0a 20 20 20 20 20 20 20 20 20 20 20 6f 66 20 66 |. of f|
000001f0 72 65 64 27 73 20 6f 6c 64 20 70 6f 73 69 74 69 |red's old positi|
00000200 6f 6e 2e 0a 0a 20 20 54 68 69 73 20 70 72 6f 67 |on... This prog|
00000210 72 61 6d 20 73 68 6f 77 73 20 74 68 65 20 69 6e |ram shows the in|
00000220 74 65 72 6d 65 64 69 61 74 65 20 73 74 65 70 73 |termediate steps|
00000230 2c 20 75 6e 64 65 72 6c 69 6e 69 6e 67 0a 20 20 |, underlining. |
00000240 74 68 65 20 70 61 69 72 20 28 66 72 65 64 2c 73 |the pair (fred,s|
00000250 61 6d 29 2e 0a 2a 2f 0a 20 0a 6d 61 69 6e 28 29 |am)..*/. .main()|
00000260 0a 7b 0a 20 64 6f 0a 20 7b 0a 20 20 70 72 69 6e |.{. do. {. prin|
00000270 74 28 22 49 6e 70 75 74 20 61 20 73 6d 61 6c 6c |t("Input a small|
00000280 69 73 68 20 6e 75 6d 62 65 72 20 28 32 2d 37 29 |ish number (2-7)|
00000290 3a 20 22 29 3b 0a 20 20 6e 20 3d 20 76 61 6c 28 |: ");. n = val(|
000002a0 69 6e 70 75 74 28 29 29 3b 0a 20 7d 20 0a 20 75 |input());. } . u|
000002b0 6e 74 69 6c 20 28 6e 20 3c 20 38 20 26 26 20 6e |ntil (n < 8 && n|
000002c0 20 3e 20 31 29 3b 0a 20 76 20 3d 20 6e 65 77 76 | > 1);. v = newv|
000002d0 65 63 74 6f 72 28 6e 29 3b 0a 20 66 61 63 74 20 |ector(n);. fact |
000002e0 3d 20 31 3b 0a 20 66 6f 72 20 28 20 6b 20 3d 20 |= 1;. for ( k = |
000002f0 6e 3b 20 6b 20 3e 20 30 3b 29 0a 20 7b 0a 20 20 |n; k > 0;). {. |
00000300 66 61 63 74 20 2a 3d 20 6b 2d 2d 3b 0a 20 20 76 |fact *= k--;. v|
00000310 5b 6b 5d 20 3d 20 6b 3b 0a 20 7d 0a 20 70 72 69 |[k] = k;. }. pri|
00000320 6e 74 28 22 3e 20 22 29 3b 0a 20 64 69 73 70 6c |nt("> ");. displ|
00000330 61 79 28 76 29 3b 0a 20 6e 65 77 6c 69 6e 65 28 |ay(v);. newline(|
00000340 29 3b 0a 20 66 6f 72 20 28 6b 20 3d 20 31 3b 20 |);. for (k = 1; |
00000350 6b 20 3c 20 66 61 63 74 3b 20 6b 2b 2b 29 0a 20 |k < fact; k++). |
00000360 20 70 65 72 6d 75 74 65 28 76 29 3b 0a 7d 0a 0a | permute(v);.}..|
00000370 64 69 73 70 6c 61 79 28 76 29 0a 7b 0a 20 6c 6f |display(v).{. lo|
00000380 63 61 6c 20 69 2c 6e 3b 0a 20 6e 20 3d 20 73 69 |cal i,n;. n = si|
00000390 7a 65 6f 66 28 76 29 3b 0a 20 66 6f 72 20 28 20 |zeof(v);. for ( |
000003a0 69 20 3d 20 30 3b 20 69 20 3c 20 6e 3b 20 69 2b |i = 0; i < n; i+|
000003b0 2b 29 0a 20 20 70 72 69 6e 74 28 76 5b 69 5d 2c |+). print(v[i],|
000003c0 22 20 22 29 3b 0a 7d 0a 0a 6e 65 77 6c 69 6e 65 |" ");.}..newline|
000003d0 28 29 0a 7b 20 70 72 69 6e 74 28 22 5c 6e 22 29 |().{ print("\n")|
000003e0 3b 20 7d 0a 0a 70 65 72 6d 75 74 65 28 76 29 0a |; }..permute(v).|
000003f0 7b 0a 20 6c 6f 63 61 6c 20 6e 2c 66 72 65 64 2c |{. local n,fred,|
00000400 73 61 6d 3b 0a 20 6e 20 3d 20 73 69 7a 65 6f 66 |sam;. n = sizeof|
00000410 28 76 29 3b 0a 20 73 61 6d 20 3d 20 6e 2d 31 3b |(v);. sam = n-1;|
00000420 0a 20 66 72 65 64 20 3d 20 73 61 6d 2d 31 3b 0a |. fred = sam-1;.|
00000430 20 77 68 69 6c 65 20 28 76 5b 66 72 65 64 5d 20 | while (v[fred] |
00000440 3e 20 76 5b 66 72 65 64 2b 31 5d 20 26 26 20 66 |> v[fred+1] && f|
00000450 72 65 64 20 3e 20 30 29 20 66 72 65 64 2d 2d 3b |red > 0) fred--;|
00000460 0a 20 77 68 69 6c 65 20 28 76 5b 73 61 6d 5d 20 |. while (v[sam] |
00000470 3c 20 76 5b 66 72 65 64 5d 20 26 26 20 73 61 6d |< v[fred] && sam|
00000480 20 3e 20 66 72 65 64 29 20 73 61 6d 2d 2d 3b 0a | > fred) sam--;.|
00000490 20 75 6e 64 65 72 6c 69 6e 65 28 66 72 65 64 2c | underline(fred,|
000004a0 73 61 6d 2c 6e 29 3b 0a 20 73 77 61 70 28 76 2c |sam,n);. swap(v,|
000004b0 66 72 65 64 2c 73 61 6d 29 3b 0a 20 64 69 73 70 |fred,sam);. disp|
000004c0 6c 61 79 28 76 29 3b 0a 20 72 65 76 65 72 73 65 |lay(v);. reverse|
000004d0 28 76 2c 66 72 65 64 2b 31 29 3b 0a 20 70 72 69 |(v,fred+1);. pri|
000004e0 6e 74 28 22 20 20 20 20 72 65 76 65 72 73 65 5c |nt(" reverse\|
000004f0 6e 3e 20 22 29 3b 0a 20 64 69 73 70 6c 61 79 28 |n> ");. display(|
00000500 76 29 3b 0a 20 6e 65 77 6c 69 6e 65 28 29 3b 0a |v);. newline();.|
00000510 7d 0a 0a 72 65 76 65 72 73 65 28 76 2c 6b 29 0a |}..reverse(v,k).|
00000520 7b 0a 20 6c 6f 63 61 6c 20 6e 2c 69 2c 68 61 6c |{. local n,i,hal|
00000530 66 2c 6f 66 66 73 65 74 3b 0a 20 6e 20 3d 20 73 |f,offset;. n = s|
00000540 69 7a 65 6f 66 28 76 29 3b 0a 20 68 61 6c 66 20 |izeof(v);. half |
00000550 3d 20 28 6e 2b 6b 29 2f 32 3b 0a 20 6f 66 66 73 |= (n+k)/2;. offs|
00000560 65 74 20 3d 20 6e 2b 6b 2d 31 3b 0a 20 66 6f 72 |et = n+k-1;. for|
00000570 20 28 69 20 3d 20 6b 3b 20 69 20 3c 20 68 61 6c | (i = k; i < hal|
00000580 66 3b 20 69 2b 2b 29 0a 20 20 20 73 77 61 70 28 |f; i++). swap(|
00000590 76 2c 69 2c 6f 66 66 73 65 74 2d 69 29 3b 0a 7d |v,i,offset-i);.}|
000005a0 0a 0a 73 77 61 70 28 76 2c 69 2c 6a 29 0a 7b 0a |..swap(v,i,j).{.|
000005b0 20 6c 6f 63 61 6c 20 77 3b 0a 20 77 20 3d 20 76 | local w;. w = v|
000005c0 5b 69 5d 3b 0a 20 76 5b 69 5d 20 3d 20 76 5b 6a |[i];. v[i] = v[j|
000005d0 5d 3b 0a 20 76 5b 6a 5d 20 3d 20 77 3b 0a 7d 0a |];. v[j] = w;.}.|
000005e0 0a 75 6e 64 65 72 6c 69 6e 65 28 69 2c 6a 2c 6e |.underline(i,j,n|
000005f0 29 0a 7b 0a 20 6c 6f 63 61 6c 20 6b 3b 0a 20 70 |).{. local k;. p|
00000600 72 69 6e 74 28 22 20 20 22 29 3b 0a 20 66 6f 72 |rint(" ");. for|
00000610 28 6b 20 3d 20 30 3b 20 6b 20 3c 20 6e 3b 20 6b |(k = 0; k < n; k|
00000620 2b 2b 29 0a 20 20 20 20 70 72 69 6e 74 28 28 28 |++). print(((|
00000630 6b 20 3d 3d 20 69 29 7c 7c 28 6b 20 3d 3d 20 6a |k == i)||(k == j|
00000640 29 29 3f 22 5e 20 22 3a 22 20 20 22 29 3b 0a 20 |))?"^ ":" ");. |
00000650 70 72 69 6e 74 28 22 20 20 20 20 73 77 61 70 5c |print(" swap\|
00000660 6e 20 20 22 29 3b 0a 7d 0a |n ");.}.|
00000669 
.