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.

    First, a picture explaining the algorithm
    image

    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)

    Also popular now: