Solve hanging lantern problem: Difference between revisions
Content added Content deleted
m (→full solution: merged the two approaches, much faster) |
(→Version 2: Made a bit more general and added more examples.) |
||
Line 937: | Line 937: | ||
===Version 2=== |
===Version 2=== |
||
{{libheader|Wren-perm}} |
{{libheader|Wren-perm}} |
||
{{libheader|Wren-big}} |
|||
Alternatively, using library methods. |
Alternatively, using library methods. |
||
<lang ecmascript>import "./perm" for Perm |
<lang ecmascript>import "./perm" for Perm |
||
import "./big" for BigInt |
|||
var listPerms = Fn.new { |a, rowSize| |
|||
⚫ | |||
⚫ | |||
⚫ | |||
var mlist = [] |
|||
⚫ | |||
⚫ | |||
lows[i] = sum |
|||
mlist = mlist + [i+1] * a[i] |
|||
⚫ | |||
var n = Perm.countDistinct(sum, a) |
|||
System.print("\nList of %(n) permutations for %(a.count) groups and lanterns per group %(a):") |
|||
var count = 0 |
|||
⚫ | |||
var curr = lows.toList |
|||
var perm = List.filled(sum, 0) |
|||
for (i in 0...sum) { |
|||
⚫ | |||
curr[p[i]-1] = curr[p[i]-1] - 1 |
|||
} |
|||
⚫ | |||
count = count + 1 |
|||
if (count % rowSize == 0) System.print() |
|||
} |
|||
if (count % rowSize != 0) System.print() |
|||
} |
|||
⚫ | |||
var n = 0 |
var n = 0 |
||
for (i in 1.. |
for (i in 1..9) { |
||
var a = (1..i).toList |
var a = (1..i).toList |
||
n = n + i |
n = n + i |
||
System.print("%(a) => %( |
System.print("%(a) => %(BigInt.multinomial(n, a))") |
||
} |
} |
||
⚫ | |||
System.print(" |
System.print("%(a) => %(BigInt.multinomial(7, a))") |
||
a = [10, 14, 12] |
|||
System.print("%(a) => %(BigInt.multinomial(36, a))") |
|||
⚫ | |||
listPerms.call([1, 2, 3], 4) |
|||
⚫ | |||
listPerms.call([1, 3, 3], 3)</lang> |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
}</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Number of permutations for |
Number of permutations for the lanterns per group shown: |
||
[1] => 1 |
[1] => 1 |
||
[1, 2] => 3 |
[1, 2] => 3 |
||
Line 968: | Line 990: | ||
[1, 2, 3, 4] => 12600 |
[1, 2, 3, 4] => 12600 |
||
[1, 2, 3, 4, 5] => 37837800 |
[1, 2, 3, 4, 5] => 37837800 |
||
[1, 2, 3, 4, 5, 6] => 2053230379200 |
|||
[1, 2, 3, 4, 5, 6, 7] => 2431106898187968000 |
|||
[1, 2, 3, 4, 5, 6, 7, 8] => 73566121315513295589120000 |
|||
[1, 2, 3, 4, 5, 6, 7, 8, 9] => 65191584694745586153436251091200000 |
|||
⚫ | |||
[10, 14, 12] => 2454860399191200 |
|||
List of 60 permutations for 3 groups and lanterns per group [1, 2, 3]: |
|||
[1, 3, 2, 6, 5, 4] [1, 3, 6, 2, 5, 4] [1, 3, 6, 5, 2, 4] [1, 3, 6, 5, 4, 2] [1, 6, 3, 2, 5, 4] |
|||
[1, 6, 3, 5, 2, 4] [1, 6, 3, 5, 4, 2] [1, 6, 5, 3, 2, 4] [1, 6, 5, 3, 4, 2] [1, 6, 5, 4, 3, 2] |
|||
[3, 1, 2, 6, 5, 4] [3, 1, 6, 2, 5, 4] [3, 1, 6, 5, 2, 4] [3, 1, 6, 5, 4, 2] [3, 2, 1, 6, 5, 4] |
|||
[3, 2, 6, 1, 5, 4] [3, 2, 6, 5, 1, 4] [3, 2, 6, 5, 4, 1] [3, 6, 2, 1, 5, 4] [3, 6, 2, 5, 1, 4] |
|||
[3, 6, 2, 5, 4, 1] [3, 6, 1, 2, 5, 4] [3, 6, 1, 5, 2, 4] [3, 6, 1, 5, 4, 2] [3, 6, 5, 1, 2, 4] |
|||
[3, 6, 5, 1, 4, 2] [3, 6, 5, 2, 1, 4] [3, 6, 5, 2, 4, 1] [3, 6, 5, 4, 2, 1] [3, 6, 5, 4, 1, 2] |
|||
[6, 3, 2, 1, 5, 4] [6, 3, 2, 5, 1, 4] [6, 3, 2, 5, 4, 1] [6, 3, 1, 2, 5, 4] [6, 3, 1, 5, 2, 4] |
|||
[6, 3, 1, 5, 4, 2] [6, 3, 5, 1, 2, 4] [6, 3, 5, 1, 4, 2] [6, 3, 5, 2, 1, 4] [6, 3, 5, 2, 4, 1] |
|||
[6, 3, 5, 4, 2, 1] [6, 3, 5, 4, 1, 2] [6, 1, 3, 2, 5, 4] [6, 1, 3, 5, 2, 4] [6, 1, 3, 5, 4, 2] |
|||
[6, 1, 5, 3, 2, 4] [6, 1, 5, 3, 4, 2] [6, 1, 5, 4, 3, 2] [6, 5, 3, 1, 2, 4] [6, 5, 3, 1, 4, 2] |
|||
[6, 5, 3, 2, 1, 4] [6, 5, 3, 2, 4, 1] [6, 5, 3, 4, 2, 1] [6, 5, 3, 4, 1, 2] [6, 5, 1, 3, 2, 4] |
|||
[6, 5, 1, 3, 4, 2] [6, 5, 1, 4, 3, 2] [6, 5, 4, 1, 3, 2] [6, 5, 4, 3, 1, 2] [6, 5, 4, 3, 2, 1] |
|||
List of permutations for 3 groups and lanterns per group [1, |
List of 140 permutations for 3 groups and lanterns per group [1, 3, 3]: |
||
[1, 3, 2, 6, 5, 4] |
[1, 4, 3, 2, 7, 6, 5] [1, 4, 3, 7, 2, 6, 5] [1, 4, 3, 7, 6, 2, 5] [1, 4, 3, 7, 6, 5, 2] |
||
[1, 3, 6, 2, 5, 4] |
[1, 4, 7, 3, 2, 6, 5] [1, 4, 7, 3, 6, 2, 5] [1, 4, 7, 3, 6, 5, 2] [1, 4, 7, 6, 3, 2, 5] |
||
[1, 3, 6, 5, 2, 4] |
[1, 4, 7, 6, 3, 5, 2] [1, 4, 7, 6, 5, 3, 2] [1, 7, 4, 3, 2, 6, 5] [1, 7, 4, 3, 6, 2, 5] |
||
[1, 3, 6, 5, 4, 2] |
[1, 7, 4, 3, 6, 5, 2] [1, 7, 4, 6, 3, 2, 5] [1, 7, 4, 6, 3, 5, 2] [1, 7, 4, 6, 5, 3, 2] |
||
[1, 6, 3, 2, 5, 4] |
[1, 7, 6, 4, 3, 2, 5] [1, 7, 6, 4, 3, 5, 2] [1, 7, 6, 4, 5, 3, 2] [1, 7, 6, 5, 4, 3, 2] |
||
[1, 6, 3, 5, 2, 4] |
[4, 1, 3, 2, 7, 6, 5] [4, 1, 3, 7, 2, 6, 5] [4, 1, 3, 7, 6, 2, 5] [4, 1, 3, 7, 6, 5, 2] |
||
[1, 6, 3, 5, 4, 2] |
[4, 1, 7, 3, 2, 6, 5] [4, 1, 7, 3, 6, 2, 5] [4, 1, 7, 3, 6, 5, 2] [4, 1, 7, 6, 3, 2, 5] |
||
[1, 6, 5, 3, 2, 4] |
[4, 1, 7, 6, 3, 5, 2] [4, 1, 7, 6, 5, 3, 2] [4, 3, 1, 2, 7, 6, 5] [4, 3, 1, 7, 2, 6, 5] |
||
[1, 6, 5, 3, 4, 2] |
[4, 3, 1, 7, 6, 2, 5] [4, 3, 1, 7, 6, 5, 2] [4, 3, 2, 1, 7, 6, 5] [4, 3, 2, 7, 1, 6, 5] |
||
[1, 6, 5, 4, 3, 2] |
[4, 3, 2, 7, 6, 1, 5] [4, 3, 2, 7, 6, 5, 1] [4, 3, 7, 2, 1, 6, 5] [4, 3, 7, 2, 6, 1, 5] |
||
[3, 1, 2, 6, 5, 4] |
[4, 3, 7, 2, 6, 5, 1] [4, 3, 7, 1, 2, 6, 5] [4, 3, 7, 1, 6, 2, 5] [4, 3, 7, 1, 6, 5, 2] |
||
[4, 3, 7, 6, 1, 2, 5] [4, 3, 7, 6, 1, 5, 2] [4, 3, 7, 6, 2, 1, 5] [4, 3, 7, 6, 2, 5, 1] |
|||
[3, 1, 6, 2, 5, 4] |
|||
[3, 1, 6, 5, 2, 4] |
[4, 3, 7, 6, 5, 2, 1] [4, 3, 7, 6, 5, 1, 2] [4, 7, 3, 2, 1, 6, 5] [4, 7, 3, 2, 6, 1, 5] |
||
[3, 1, 6, 5, 4, 2] |
[4, 7, 3, 2, 6, 5, 1] [4, 7, 3, 1, 2, 6, 5] [4, 7, 3, 1, 6, 2, 5] [4, 7, 3, 1, 6, 5, 2] |
||
[4, 7, 3, 6, 1, 2, 5] [4, 7, 3, 6, 1, 5, 2] [4, 7, 3, 6, 2, 1, 5] [4, 7, 3, 6, 2, 5, 1] |
|||
[3, 2, 1, 6, 5, 4] |
|||
[4, 7, 3, 6, 5, 2, 1] [4, 7, 3, 6, 5, 1, 2] [4, 7, 1, 3, 2, 6, 5] [4, 7, 1, 3, 6, 2, 5] |
|||
[3, 2, 6, 1, 5, 4] |
|||
[3, 2, 6, 5, 1, 4] |
[4, 7, 1, 3, 6, 5, 2] [4, 7, 1, 6, 3, 2, 5] [4, 7, 1, 6, 3, 5, 2] [4, 7, 1, 6, 5, 3, 2] |
||
[3, 2, 6, 5, 4, 1] |
[4, 7, 6, 3, 1, 2, 5] [4, 7, 6, 3, 1, 5, 2] [4, 7, 6, 3, 2, 1, 5] [4, 7, 6, 3, 2, 5, 1] |
||
[4, 7, 6, 3, 5, 2, 1] [4, 7, 6, 3, 5, 1, 2] [4, 7, 6, 1, 3, 2, 5] [4, 7, 6, 1, 3, 5, 2] |
|||
[3, 6, 2, 1, 5, 4] |
|||
[3, 6, 2, 5, 1, 4] |
[4, 7, 6, 1, 5, 3, 2] [4, 7, 6, 5, 1, 3, 2] [4, 7, 6, 5, 3, 1, 2] [4, 7, 6, 5, 3, 2, 1] |
||
[3, 6, 2, 5, 4, 1] |
[7, 4, 3, 2, 1, 6, 5] [7, 4, 3, 2, 6, 1, 5] [7, 4, 3, 2, 6, 5, 1] [7, 4, 3, 1, 2, 6, 5] |
||
[3, 6, 1, 2, 5, 4] |
[7, 4, 3, 1, 6, 2, 5] [7, 4, 3, 1, 6, 5, 2] [7, 4, 3, 6, 1, 2, 5] [7, 4, 3, 6, 1, 5, 2] |
||
[3, 6, 1, 5, 2, 4] |
[7, 4, 3, 6, 2, 1, 5] [7, 4, 3, 6, 2, 5, 1] [7, 4, 3, 6, 5, 2, 1] [7, 4, 3, 6, 5, 1, 2] |
||
[3, 6, 1, 5, 4, 2] |
[7, 4, 1, 3, 2, 6, 5] [7, 4, 1, 3, 6, 2, 5] [7, 4, 1, 3, 6, 5, 2] [7, 4, 1, 6, 3, 2, 5] |
||
[3, 6, 5, 1, 2, 4] |
[7, 4, 1, 6, 3, 5, 2] [7, 4, 1, 6, 5, 3, 2] [7, 4, 6, 3, 1, 2, 5] [7, 4, 6, 3, 1, 5, 2] |
||
[3, 6, 5, 1, 4, 2] |
[7, 4, 6, 3, 2, 1, 5] [7, 4, 6, 3, 2, 5, 1] [7, 4, 6, 3, 5, 2, 1] [7, 4, 6, 3, 5, 1, 2] |
||
[3, 6, 5, 2, 1, 4] |
[7, 4, 6, 1, 3, 2, 5] [7, 4, 6, 1, 3, 5, 2] [7, 4, 6, 1, 5, 3, 2] [7, 4, 6, 5, 1, 3, 2] |
||
[3, 6, 5, 2, 4, 1] |
[7, 4, 6, 5, 3, 1, 2] [7, 4, 6, 5, 3, 2, 1] [7, 1, 4, 3, 2, 6, 5] [7, 1, 4, 3, 6, 2, 5] |
||
[3, 6, 5, 4, 2, 1] |
[7, 1, 4, 3, 6, 5, 2] [7, 1, 4, 6, 3, 2, 5] [7, 1, 4, 6, 3, 5, 2] [7, 1, 4, 6, 5, 3, 2] |
||
[3, 6, 5, 4, 1, 2] |
[7, 1, 6, 4, 3, 2, 5] [7, 1, 6, 4, 3, 5, 2] [7, 1, 6, 4, 5, 3, 2] [7, 1, 6, 5, 4, 3, 2] |
||
[6, 3, 2, 1, 5, 4] |
[7, 6, 4, 3, 1, 2, 5] [7, 6, 4, 3, 1, 5, 2] [7, 6, 4, 3, 2, 1, 5] [7, 6, 4, 3, 2, 5, 1] |
||
[6, 3, 2, 5, 1, 4] |
[7, 6, 4, 3, 5, 2, 1] [7, 6, 4, 3, 5, 1, 2] [7, 6, 4, 1, 3, 2, 5] [7, 6, 4, 1, 3, 5, 2] |
||
[6, 3, 2, 5, 4, 1] |
[7, 6, 4, 1, 5, 3, 2] [7, 6, 4, 5, 1, 3, 2] [7, 6, 4, 5, 3, 1, 2] [7, 6, 4, 5, 3, 2, 1] |
||
[6, 3, 1, 2, 5, 4] |
[7, 6, 1, 4, 3, 2, 5] [7, 6, 1, 4, 3, 5, 2] [7, 6, 1, 4, 5, 3, 2] [7, 6, 1, 5, 4, 3, 2] |
||
[6, 3, 1, 5, 2, 4] |
[7, 6, 5, 4, 1, 3, 2] [7, 6, 5, 4, 3, 1, 2] [7, 6, 5, 4, 3, 2, 1] [7, 6, 5, 1, 4, 3, 2] |
||
[6, 3, 1, 5, 4, 2] |
|||
[6, 3, 5, 1, 2, 4] |
|||
[6, 3, 5, 1, 4, 2] |
|||
[6, 3, 5, 2, 1, 4] |
|||
[6, 3, 5, 2, 4, 1] |
|||
[6, 3, 5, 4, 2, 1] |
|||
[6, 3, 5, 4, 1, 2] |
|||
⚫ | |||
[6, 1, 3, 5, 2, 4] |
|||
[6, 1, 3, 5, 4, 2] |
|||
[6, 1, 5, 3, 2, 4] |
|||
[6, 1, 5, 3, 4, 2] |
|||
[6, 1, 5, 4, 3, 2] |
|||
[6, 5, 3, 1, 2, 4] |
|||
[6, 5, 3, 1, 4, 2] |
|||
[6, 5, 3, 2, 1, 4] |
|||
[6, 5, 3, 2, 4, 1] |
|||
[6, 5, 3, 4, 2, 1] |
|||
[6, 5, 3, 4, 1, 2] |
|||
[6, 5, 1, 3, 2, 4] |
|||
[6, 5, 1, 3, 4, 2] |
|||
[6, 5, 1, 4, 3, 2] |
|||
⚫ | |||
[6, 5, 4, 3, 1, 2] |
|||
[6, 5, 4, 3, 2, 1] |
|||
</pre> |
</pre> |