1 more non-recursive algorithm for generating all partitions of an integer
I want to offer Habra my own version of the non-recursive algorithm for generating all partitions of an integer in lexicographical order. The May note served as a push. The proposed algorithm also has the idea of transferring an extremely right element.
The reasons for which I wanted to offer my own version of the algorithm is that in all the algorithms I have seen there is an array search at every step. It seemed to me somewhat redundant. We will consider the algorithm itself as a description of the permutation of unit cubes (squares) in the plane (from right to left) and their periodic scattering along the horizontal axis.
Details below.
Beginning Algorithm
')
We have an x_massiv array of dimension NN of 1 (all the squares are in one 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 loop
It may repeat in the partition several more times, so we use another cycle.
For JJ = 1 ... kol_hh (kol_hh = Int (NN / hh) is 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 by jj). Calculate the values of ost, ost1 = NN - hh * jj - the residuals that must be distributed in the main loop and the initial coordinates
Main loop
We move the cube from the place from_x to the place to_x (x_massiv (from_x) - and x_massiv (to_x) ++) checking 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 source codes). An array search is not always needed. I think this is a plus. If necessary, the remainder of the partition ost1 is recalculated.
end of main loop
end of cycle jj
end of cycle hh
I understand that the description is rather clumsy, because This is a translation from a programming language to a natural one. For those who are familiar with the Vb Vbf Vbs syntax, it is probably easier to watch the script right away, for others - the text is go. Plus a picture.
My arrays below start at 1.
An example of an algorithm for vbs
VBS-script (for Win) - start is better to do how to open in the command line:
An example of an algorithm on golang (as I can, I just play around with the language)
You can run 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 lexicographical division of the number, but in the reverse order. It surprises me.
References:
[1] V.Lipsky. Combinatorics for programmers. (Moscow, World Publishing, 1988. p 63)
The reasons for which I wanted to offer my own version of the algorithm is that in all the algorithms I have seen there is an array search at every step. It seemed to me somewhat redundant. We will consider the algorithm itself as a description of the permutation of unit cubes (squares) in the plane (from right to left) and their periodic scattering along the horizontal axis.
Details below.
First a picture explaining the algorithm.
Beginning Algorithm
')
We have an x_massiv array of dimension NN of 1 (all the squares are in one 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:
- coordinate where to put the cube to_x
- coordinate from where to shoot the cube from_x
- the number of cubes that should 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 loop
It may repeat in the partition several more times, so we use another cycle.
For JJ = 1 ... kol_hh (kol_hh = Int (NN / hh) is 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 by jj). Calculate the values of ost, ost1 = NN - hh * jj - the residuals that must be distributed in the main loop and the initial coordinates
- from_x = NN - jj * (hh - 1)
- to_x = jj + 1
Main loop
We move the cube from the place from_x to the place to_x (x_massiv (from_x) - and x_massiv (to_x) ++) checking 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 spilling
x_massiv (from_x) <= 2 no need to scatter - Proximity to_x and from_x
- residue size ost1
All possible combinations of conditions (details in source codes). An array search is not always needed. I think this is a plus. If necessary, the remainder of the partition ost1 is recalculated.
- If necessary, to_x is searched. Search interval is less than 1..NN. to_x is searched for as the coordinate with the lowest value, search in descending order (from right to left)
- If necessary, the scattering of residues is carried out, to the right of that place it became where there are more than 2 cubes (conditions are visible from the text of the vbs script and / or go program)
end of main loop
end of cycle jj
end of cycle hh
I understand that the description is rather clumsy, because This is a translation from a programming language to a natural one. For those who are familiar with the Vb Vbf Vbs syntax, it is probably easier to watch the script right away, for others - the text is go. Plus a picture.
My arrays below start at 1.
An example of an algorithm for vbs
VBS-script (for Win) - start is better to do how to open in the command line:
Vbs algorithm
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 of an algorithm on golang (as I can, I just play around with the language)
You can run 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 proportion of searches in the total number of partitions of a little more than one-third (for numbers less than 30)
- With the growth of the number to be broken, the share of searches decreases to one quarter (for numbers over 70), for 100 it did not pass
- Perhaps the reduction in the number of searches speeds up the algorithm somewhat, but on the other hand makes it a bit more difficult.
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 lexicographical division of the number, but in the reverse order. It surprises me.
References:
[1] V.Lipsky. Combinatorics for programmers. (Moscow, World Publishing, 1988. p 63)
Source: https://habr.com/ru/post/330046/
All Articles