Solve hanging lantern problem
You are encouraged to solve this task according to the task description, using any language you may know.
There are some groups of lantern hanging on the ceil. Each group contais one or more lanterns. Each time you can fetch one lantern. Now you need to get all these lanterns down, but you can only fetch the one in the bottom of the group. The qustion is how many ways are there to do this.
For example, there are some lanterns hanging like this:
🏮 🏮 🏮
🏮 🏮
🏮
Number these lanterns:
1 2 4
3 5
6
You can take like this: [6,3,5,2,4,1] or [3,1,6,5,2,4]
But not: [6,3,2,4,5,1] because at that time 5 is under 4.
There are 60 ways to take them down.
- Task
Input:
First an integer (n): the number of groups.
Then n integers: the number of lanterns each group has.
Output:
An integer: the number of sequences.
For example, the input of the example above could be:
3 1 2 3
And the output is:
60
- Optional task
Output all the sequences using this format:
[a,b,c,…] [b,a,c,…] ……
Phix
- Output:
with javascript_semantics include mpfr.e function get_lantern(integer n) mpz z = mpz_init() mpz_bin_uiui(z,n*(n+1)/2,n) if n>1 then mpz_mul(z,z,get_lantern(n-1)) end if return z end function for n=1 to 8 do printf(1,"%v = %s\n",{tagset(n),mpz_get_str(get_lantern(n))}) end for
{1} = 1
{1,2} = 3
{1,2,3} = 60
{1,2,3,4} = 12600
{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
Picat
<lang Picat>main =>
run_lantern().
run_lantern() =>
N = read_int(),
A = [],
foreach(_ in 1..N)
A := A ++ [read_int()]
end,
println(A),
println(lantern(A)),
nl.
table lantern(A) = Res =>
Arr = copy_term(A),
Res = 0,
foreach(I in 1..Arr.len)
if Arr[I] != 0 then
Arr[I] := Arr[I] - 1,
Res := Res + lantern(Arr),
Arr[I] := Arr[I] + 1
end
end,
if Res == 0 then
Res := 1
end.</lang>
Some tests: <lang Picat>main =>
A = [1,2,3], println(lantern(A)), foreach(N in 1..8) println(1..N=lantern(1..N)) end, nl.</lang>
- Output:
60 [1] = 1 [1,2] = 3 [1,2,3] = 60 [1,2,3,4] = 12600 [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
The sequence of lantern(1..N) is the OEIS sequence A022915 ("Multinomial coefficients (0, 1, ..., n)! = C(n+1,2)!/(0!*1!*2!*...*n!)").
Python
- Recursive version
<lang python> def getLantern(arr):
res = 0
for i in range(0, n):
if arr[i] != 0:
arr[i] -= 1
res += getLantern(arr)
arr[i] += 1
if res == 0:
res = 1
return res
a = [] n = int(input()) for i in range(0, n):
a.append(int(input()))
print(getLantern(a)) </lang>
VBA
- See Visual Basic
Visual Basic
- Main code
<lang vb> Dim n As Integer, c As Integer Dim a() As Integer
Private Sub Command1_Click()
Dim res As Integer If c < n Then Label3.Caption = "Please input completely.": Exit Sub res = getLantern(a()) Label3.Caption = "Result：" + Str(res)
End Sub
Private Sub Text1_Change()
If Val(Text1.Text) <> 0 Then
n = Val(Text1.Text)
ReDim a(1 To n) As Integer
End If
End Sub
Private Sub Text2_KeyPress(KeyAscii As Integer)
If KeyAscii = Asc(vbCr) Then
If Val(Text2.Text) = 0 Then Exit Sub
c = c + 1
If c > n Then Exit Sub
a(c) = Val(Text2.Text)
List1.AddItem Str(a(c))
Text2.Text = ""
End If
End Sub
Function getLantern(arr() As Integer) As Integer
Dim res As Integer
For i = 1 To n
If arr(i) <> 0 Then
arr(i) = arr(i) - 1
res = res + getLantern(arr())
arr(i) = arr(i) + 1
End If
Next i
If res = 0 Then res = 1
getLantern = res
End Function</lang>
- Form code
<lang vb> VERSION 5.00 Begin VB.Form Form1
Caption = "Get Lantern"
ClientHeight = 4410
ClientLeft = 120
ClientTop = 465
ClientWidth = 6150
LinkTopic = "Form1"
ScaleHeight = 4410
ScaleWidth = 6150
StartUpPosition = 3
Begin VB.CommandButton Command1
Caption = "Start"
Height = 495
Left = 2040
TabIndex = 5
Top = 3000
Width = 1935
End
Begin VB.ListBox List1
Height = 1320
Left = 360
TabIndex = 4
Top = 1440
Width = 5175
End
Begin VB.TextBox Text2
Height = 855
Left = 3360
TabIndex = 1
Top = 480
Width = 2175
End
Begin VB.TextBox Text1
Height = 855
Left = 360
TabIndex = 0
Top = 480
Width = 2175
End
Begin VB.Label Label3
Height = 495
Left = 2040
TabIndex = 6
Top = 3720
Width = 2295
End
Begin VB.Label Label2
Caption = "Number Each"
Height = 375
Left = 3960
TabIndex = 3
Top = 120
Width = 1695
End
Begin VB.Label Label1
Caption = "Total"
Height = 255
Left = 960
TabIndex = 2
Top = 120
Width = 1455
End
End Attribute VB_Name = "Form1" Attribute VB_GlobalNameSpace = False Attribute VB_Creatable = False Attribute VB_PredeclaredId = True Attribute VB_Exposed = False</lang>
Wren
Version 1
The result for n == 5 is slow to emerge. <lang ecmascript>var lantern // recursive function lantern = Fn.new { |n, a|
var count = 0
for (i in 0...n) {
if (a[i] != 0) {
a[i] = a[i] - 1
count = count + lantern.call(n, a)
a[i] = a[i] + 1
}
}
if (count == 0) count = 1
return count
}
System.print("Number of permutations for n (<= 5) groups and lanterns per group [1..n]:") var n = 0 for (i in 1..5) {
var a = (1..i).toList
n = n + 1
System.print("%(a) => %(lantern.call(n, a))")
}</lang>
- Output:
Number of permutations for n (<= 5) groups and lanterns per group [1..n]: [1] => 1 [1, 2] => 3 [1, 2, 3] => 60 [1, 2, 3, 4] => 12600 [1, 2, 3, 4, 5] => 37837800
Version 2
Alternatively, using library methods. <lang ecmascript>import "./perm" for Perm
System.print("Number of permutations for n (<= 5) groups and lanterns per group [1..n]:") var n = 0 for (i in 1..5) {
var a = (1..i).toList
n = n + i
System.print("%(a) => %(Perm.countDistinct(n, a))")
}
System.print("\nList of permutations for 3 groups and lanterns per group [1, 2, 3]:") var lows = [1, 3, 6] for (p in Perm.listDistinct([1, 2, 2, 3, 3, 3])) {
var curr = lows.toList
var perm = List.filled(6, 0)
for (i in 0..5) {
perm[i] = curr[p[i]-1]
curr[p[i]-1] = curr[p[i]-1] - 1
}
System.print(perm)
}</lang>
- Output:
Number of permutations for n (<= 5) groups and lanterns per group [1..n]: [1] => 1 [1, 2] => 3 [1, 2, 3] => 60 [1, 2, 3, 4] => 12600 [1, 2, 3, 4, 5] => 37837800 List of 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]