Combinatorics


   Program solutions for generating combinations, variations and permutations for any number of variables are shown as very useful to apply in various specialistic purposes... At these pages, for example, it makes the basic framework in the program of Factor analysis and the Program for findig the non-attacking pieces on the chess board with "backtrack" method, and also well it served at the Program for homogenezing meal categorized by various parameters of the wheat in the silo cells!          

   Tetszőleges számú változók kombinációit, variációit valamint permutációit eredményező programmegoldások nagyon eredményesen alkalmazhatók a legkülönbözőbb speciális szükségletekre... Az itt bemutatott programoknál pl. alapvázát képezik úgy a Faktoranalízisben, mint a "Backtrack" módszert felhasználó sakkfigurákra vonatkozó programban is, de ugyanolyan jónak mutatkozott a liszt homogenizációs problémájának megoldására is a silókban levő búza különböző paramétereinek függvényében!      

   Programska rešenja za generisanje kombinacija, varijacija ili permutacija za proizvoljan broj varijabli se pokazuju kao vrlo korisne u primeni najrazlicitijih specijalistickih potreba... Na ovim stranicama npr. one cine osnovni kostur  programa Faktorska analiza kao i Programa za nalaženje svih nenapadajucih šahovskih figura po takozvanoj "backtrack" metodi, a isto je tako dobro poslužio i u Programu za homogenizaciju brašna po raznim parametrima pšenice u silo celijama! 

 

Listing for generating COMBINATIONS with minimal required codes in BASIC:                                                

 

The similar solution but in structural form in ZIM:  

 

 

Captured screen from chess -table analysis:

 

 

 

 

 

 

 

 

 

 

 

Download program Backtrack_V2

The original "Backtrack_V2" combinatorial program represents an easy way for enumerating (k) non-attacking chess pieces on nXn sized rectangular boards. Although it's originally intended for demonstration of the backtracking process, it's really uses by itself a much more sophisticated method, a generator of combinations and permutations, which gives exatly the required number of the rook positions! By filtering out the diagonal attacks we can simply get the satisfactory queen positions! This technique is also noticed and rather used by Raymond Hettingers (MIT, 2009) in his Python solutions. The bishop attacks, however, can't produce directly "in passing" by this way, but the obtained results for bishops equals to of what V.Kotesovec called as "composite pieces: bishop + semi-rook" (example.: A185056 -OEIS)

Release notes to the enhanced Backtrack_V4 Pro version:

  • The main reason for the 'Professional' adjective is due to its possibility of recording the intermediate results of the enumerating process (by pressing "s" for Save) and continuing it later at any time (by pressing "l" for Load), even on other, faster computer! There is also included a daily automatic recording, preventing thus loss the results of several months / years of working, which may be otherwise occur because of a power failure or other reason of interruption the program, or simply by a forgotten manually saveing! Moreover, after completing one task of enumeration, the program automatically save the final result to a textual file with *.all extension!
  • Manual Save and Load are available only when Pause is setting to 1.
  • Automatic recordings are available if both the Pause and Display settings are turn to 0.
  • After the initial settings while program is running, alternately pressing the button "p" leads to change Pause from one stage to another. The P=0 position enables continually work of the program, while the P=1 position makes pause after each found combination, up to pressure the Enter key.
  • The Display option can be changed the similar way, by alternately pressing the button "d".
  • The program is not limited to the size of the board, but for n>16, the D=1 display setting only prints the coordinates of the peaces, instead of displaying them on the table!

    The  Backtrack_V5 Pro version shows all previous enhanced features on a simple menu.

    The  Backtrack_V6 Pro version is specially worked out for new opportunities of enumerating the diagonally attacked positions by various criteria, but is not publicly presented.

    The  Backtrack_V7 Pro version incorporates all possibilities of the previous two versions. So now, in addition to finding all non-attacking positions, there are also enabled enumeration of such queen positions where they make various diagonal attacks with each other, and the number of these cases are shown according to columns allocated by the first Queen!

  • Menu options are also increased by one function, namely, the Find function, so pressing the "f" button will stops the counting process when find the next available position that satisfies the given conditions, i.e. some specified kind of a diagonally attack.
  • The computed values for columns are themselves form a sequence, but are particularly interesting their sums, which are also generate sequences with terms depends on the size of the observed table, and are otherwise usually appears as a known sequences in the OEIS.  (See the example below!)
  • The importance of their analysis just increases and confirms by the fact that these results can often lead in context of a variety of mathematical areas (combinatorics, number theory, internal stable matrices, graph theory, etc.) or even a physical phenomena or chemical processes!

    n

     Counting results of exatly 3 diagonal attacks made by 3 queens shown by columns

    Sums

    3

    2

    2

    4

    8

    4

     

     

     

     

     

     

    12

    5

    20

    14

    6

     

     

     

     

     

    40

    6

    40

    32

    20

    8

     

     

     

     

    100

    7

    70

    60

    44

    26

    10

     

     

     

    210

    8

    112

    100

    80

    56

    32

    12

     

     

    392

    9

    168

    154

    130

    100

    68

    38

    14

     

    672

    10

    240

    224

    196

    160

    120

    80

    44

    16

    1080

    ...                                         ... ...      
    A007290 A159920

    2*A006503

    2*A060488

                            A017617 A016933 A008911

     

     

     

     

     

     

     

     








     

    References:http://www.dejanristanovic.com/refer/kombin.htm

    - Copyright: A.Pinter, 1994 -

    This webpage updated Oct 10, 2015