Another 1 non-recursive algorithm for generating all integer partitions
I want to offer Habr own version of the non-recursive algorithm for generating all integer partitions in lexicographic order. The impetus was the May note . The proposed algorithm also has the idea of transferring the rightmost element.
The reasons why I wanted to offer my own version of the algorithm is that in all the algorithms I saw at every step there is a search in the array. It seemed to me somewhat redundant. The algorithm itself will be considered as a description of the permutation of individual cubes (squares) on the plane (from right to left) and their periodic scattering along the horizontal axis.
Details below.
Beginning of the Algorithm
We have an x_massiv array of dimension NN of 1 (the squares all lie in the same row along the X axis) - the index is the X coordinate, the value of the x_massiv array is the number of cubes. We introduce the following additional variables:
The first number in the partition can be from 2 to NN, so we use the For hh = 2 ... NN cycle.
It can be repeated several times in the partition, so we use another
For JJ = 1 ... kol_hh (kol_hh = Int (NN / hh) - the whole part) in which we form from one or more elements. Before the start of the main loop, we have a filled rectangle (dimensions hh on jj). We calculate the values ost, ost1 = NN - hh * jj - the residues that must be posted in the main cycle and the initial coordinates
The main loop We
rearrange the cube from the place from_x to the place to_x (x_massiv (from_x) - and x_massiv (to_x) ++) check for exit from the main loop according to the conditions:
Recalculation from_x and to_x depending on independent conditions:
All possible combinations of conditions (details in the source codes). An array search is not always needed. I consider this a plus. If necessary, the remainder of the partition ost1 is recalculated.
end of the main loop
end of the loop jj
end of the loop hh
I understand that the description is rather clumsy, because it is a translation from a programming language into a natural one. For those who are familiar with the syntax of Vb Vbf Vbs, it is probably easier to immediately look at the script, for the rest - text on go. Plus a picture.
My arrays below start with 1.
An example of an algorithm for a vbs
VBS-script (for Win) - it’s better to do the launch as opening in the command line:
An example algorithm on golang (as I can, I only dabble in language) You
can run it on golang.org/# :
Observation
For those who got to the end of the note: if we consider the number of cubes along the Y axis (vertical), then their number will also be a lexicographic partition of the number, but in the reverse order. It surprises me.
References:
[1] V. Lipsky. Combinatorics for programmers. (Moscow, Mir publishing house, 1988. p. 63)
The reasons why I wanted to offer my own version of the algorithm is that in all the algorithms I saw at every step there is a search in the array. It seemed to me somewhat redundant. The algorithm itself will be considered as a description of the permutation of individual cubes (squares) on the plane (from right to left) and their periodic scattering along the horizontal axis.
Details below.
First, a picture explaining the algorithm
Beginning of the Algorithm
We have an x_massiv array of dimension NN of 1 (the squares all lie in the same row along the X axis) - the index is the X coordinate, the value of the x_massiv array is the number of cubes. We introduce the following additional variables:
- the coordinate where to put the cube to_x
- coordinate from where to remove from_x cube
- the number of cubes to be scattered ost and ost1
The first number in the partition can be from 2 to NN, so we use the For hh = 2 ... NN cycle.
It can be repeated several times in the partition, so we use another
For JJ = 1 ... kol_hh (kol_hh = Int (NN / hh) - the whole part) in which we form from one or more elements. Before the start of the main loop, we have a filled rectangle (dimensions hh on jj). We calculate the values ost, ost1 = NN - hh * jj - the residues that must be posted in the main cycle and the initial coordinates
- from_x = NN - jj * (hh - 1)
- to_x = jj + 1
The main loop We
rearrange the cube from the place from_x to the place to_x (x_massiv (from_x) - and x_massiv (to_x) ++) check for exit from the main loop according to the conditions:
- x_massiv (to_x) = hh
- or ost <= 1
- or x_massiv (to_x - 1) = hh And to_x = from_x
Recalculation from_x and to_x depending on independent conditions:
- x_massiv (from_x)> 2 condition for
scattering x_massiv (from_x) <= 2 it is not necessary to scatter - Proximity to_x and from_x
- residue size ost1
All possible combinations of conditions (details in the source codes). An array search is not always needed. I consider this a plus. If necessary, the remainder of the partition ost1 is recalculated.
- If necessary, a to_x search is performed. search interval less than 1..NN. to_x is searched as the coordinate with the smallest value, descending search (from right to left)
- If necessary, a scattering of residues is carried out, to the right of that place where there are more than 2 cubes (conditions are visible from the text of the vbs script and / or go program)
end of the main loop
end of the loop jj
end of the loop hh
I understand that the description is rather clumsy, because it is a translation from a programming language into a natural one. For those who are familiar with the syntax of Vb Vbf Vbs, it is probably easier to immediately look at the script, for the rest - text on go. Plus a picture.
My arrays below start with 1.
An example of an algorithm for a vbs
VBS-script (for Win) - it’s better to do the launch as opening in the command line:
Algorithm on vbs
Dim ii , jj , kkk
Dim summ , str_rez, iii
Dim from_x , to_x
Dim ost , ost1 , flag_poisk , flag_razb
Dim kol_razb , kol_poisk
Dim hh , kol_hh
str_rez = inputbox ( "Введите число для разбиений N")
if str_rez <> vbNullString then
if IsNumeric (str_rez) then
NN = cint(str_rez)
else
WScript.Quit
end if
else
WScript.Quit
end if
ReDim x_massiv(NN)
For ii = 1 To NN - 1
x_massiv(ii) = 1
Next
str_rez = vbNullString
For iii = 1 To NN
str_rez = str_rez + "1;"
Next
'''вывод
WScript.Echo str_rez
kol_razb = 1
For hh = 2 To NN ' - 1
kol_hh = Int(NN / hh)
For jj = 1 To kol_hh
''' инициализация
For ii = 1 To jj
x_massiv(ii) = hh
Next
from_x = NN - jj * (hh - 1)
to_x = jj + 1
ost = NN - hh * jj
ost1 = ost
For ii = to_x To from_x
x_massiv(ii) = 1
Next
Do
str_rez = vbNullString
For iii = 1 To from_x
If x_massiv(iii) > 0 Then
str_rez = str_rez + CStr(x_massiv(iii)) + ";"
Else
Exit For
End If
Next
'''вывод
WScript.Echo str_rez
kol_razb = kol_razb + 1
If ost <= 1 Then
Exit Do
End If
''' перенос начинаем переставлять кубики
''' из места from_x на место to_x
x_massiv(from_x) = x_massiv(from_x) - 1
x_massiv(to_x) = x_massiv(to_x) + 1
If x_massiv(to_x) = hh Then
Exit Do
End If
If x_massiv(to_x - 1) = hh And to_x = from_x Then
Exit Do
End If
flag_poisk = False
flag_razb = False
If x_massiv(to_x) > 2 Then
If to_x + 1 = from_x Then
ost1 = x_massiv(from_x)
If ost1 = 0 Then
from_x = from_x - 1
flag_poisk = True
Else
If ost1 = 1 Then
flag_poisk = True
Else
flag_razb = True
ost1 = x_massiv(from_x)
from_x = to_x + ost1
to_x = to_x + 1
End If
End If
Else ''' to_x + 1 != from_x
flag_razb = True
ost1 = ost1 - x_massiv(to_x)
from_x = to_x + ost1
to_x = to_x + 1
End If
Else
If x_massiv(from_x) = 0 Then
from_x = from_x - 1
End If
If to_x + 1 < from_x Then
to_x = to_x + 1
ost1 = ost1 - 2
Else
flag_poisk = True
End If
End If
If flag_poisk Then
kol_poisk = kol_poisk + 1
flag_poisk = False
summ = x_massiv(from_x)
''поиск to_x. интервал меньше чем 1..NN
For kkk = from_x - 1 To jj + 1 Step -1
summ = summ + x_massiv(kkk)
If x_massiv(kkk) < x_massiv(kkk - 1) Then
to_x = kkk
ost1 = summ
flag_poisk = True
Exit For
End If
Next
If Not flag_poisk Then
to_x = jj + 1
ost1 = ost
End If
End If ''' flag_poisk
If flag_razb Then '' рассыпаем
For kkk = to_x To from_x
x_massiv(kkk) = 1
Next
End If
Loop
Next
Next
MsgBox "Разбиений = " + CStr(kol_razb) + vbCrLf + " Поисков =" + CStr(kol_poisk)
An example algorithm on golang (as I can, I only dabble in language) You
can run it on golang.org/# :
Golang algorithm
//разбиение целого числа в лексикографическом порядке
// razbien_int project main.go
package main
import (
"fmt"
)
func main() {
var massiv [100]int32
var NN, HH, kol_HH int32
var ii, jj, kol_poisk, kol_per, kol_rez int32
var from_x, to_x int32 // указатели откуда и куда переносим 1
var ost, ost1, summ int32
var flag_poisk, flag_per byte
NN = 20 // число которое разбиваем <=100
kol_poisk = 0 //кол-во поисков
kol_per = 0 //кол-во рассыпаний переукладок
fmt.Println("NN =", NN)
for ii = 1; ii <= NN; ii++ {
massiv[ii] = 1
}
from_x = NN
/// pr_mass(NN)
fmt.Println(massiv[1:NN]) // печать 1
kol_rez = 1 /// первый результат
for HH = 2; HH <= NN; HH++ { // величина превого элемента в разбиении
kol_HH = NN / HH // максимальное число повторов первого элемента HH
for jj = 1; jj <= kol_HH; jj++ {
// ini 1 заполнение первым элементом
for ii = 1; ii <= jj; ii++ {
massiv[ii] = HH
}
from_x = NN - jj*(HH-1)
to_x = jj + 1
ost = NN - HH*jj
ost1 = ost
// ini 2 заполнение хвоста 1
for ii = to_x; ii <= from_x; ii++ {
massiv[ii] = 1
}
// сформирован массив из первых значений HH и 1
// основной цикл
for {
fmt.Println(massiv[1 : from_x+1]) // печать
///pr_mass(from_x)
kol_rez++
if ost <= 1 {
break
}
massiv[from_x]--
massiv[to_x]++
if massiv[to_x] == HH {
break
}
if massiv[to_x-1] == HH && to_x == from_x {
break
}
flag_poisk = 0
flag_per = 0
if massiv[to_x] > 2 {
if to_x+1 == from_x {
ost1 = massiv[from_x]
if ost1 == 0 {
from_x--
flag_poisk = 1
} else {
if ost1 == 1 {
flag_poisk = 1
} else {
flag_per = 1
ost1 = massiv[from_x]
from_x = to_x + ost1
to_x++
}
}
} else { /// to_x+1 != from_x
flag_per = 1
ost1 = ost1 - massiv[to_x]
from_x = to_x + ost1
to_x++
}
} else { /// <=2
if massiv[from_x] == 0 {
from_x--
}
if to_x+1 < from_x {
to_x++
ost1 = ost1 - 2
} else {
flag_poisk = 1
}
}
if flag_poisk == 1 {
kol_poisk++
flag_poisk = 0
summ = massiv[from_x]
for kkk := from_x - 1; kkk >= jj+1; kkk-- {
summ = summ + massiv[kkk]
if massiv[kkk] < massiv[kkk-1] {
to_x = kkk
ost1 = summ
flag_poisk = 1
break
}
}
if flag_poisk == 0 {
to_x = jj + 1
ost1 = ost
}
}
if flag_per == 1 {
kol_per++ /// рассыпаем
for kkk := to_x; kkk <= from_x; kkk++ {
massiv[kkk] = 1
}
}
}
}
}
fmt.Println("Число разбиений =", kol_rez)
fmt.Println("количество поисков =", kol_poisk)
fmt.Println("количество рассыпаний =", kol_per)
}
Observation
- The share of searches in the total number of partitions is slightly more than one third (for numbers less than 30)
- With the growth of the number being split, the percentage of searches decreases to one quarter (for numbers over 70), for 100 did not go over
- Perhaps a decrease in the number of searches speeds up the algorithm somewhat, but on the other hand makes it a little more complicated.
For those who got to the end of the note: if we consider the number of cubes along the Y axis (vertical), then their number will also be a lexicographic partition of the number, but in the reverse order. It surprises me.
References:
[1] V. Lipsky. Combinatorics for programmers. (Moscow, Mir publishing house, 1988. p. 63)