On an application of multidimensional arrays Krasimir Yordzhev∗ South-WestUniversity”NeofitRilski”, Blagoevgrad,Bulgaria Abstract 6 Thisarticlediscussessomedifficultiesintheimplementationofcombinatorialalgorithmsassociated 1 with the choice of all elements with certain properties among the elements of a set with great 0 cardinality.The problem has been resolved by using multidimensional arrays. Illustration of the 2 methodis a solutionof the problemof obtainingone representativefromeach equivalenceclass n a with respect to the described in the article equivalence relation in the set of all m ∼ n binary J matrices. Thisequivalencerelationhasanapplicationinthemathematicalmodelinginthetextile 5 industry. 1 Keywords:binarymatrix;equivalencerelation;factor-set;cardinality;multidimensionalarray ] 2010MathematicsSubjectClassification:05B20;68P05 S D . 1 Introduction and task formulation s c [ Thefollowingproblemoftenoccursincomputerscience: 1 v Problem1.1. LetM beafinitesetandlet∼beanequivalencerelationinM. Describeandimple- 8 mentanalgorithmthatreceivesexactlyonerepresentativefromeachequivalenceclasswithrespect 2 to∼. 9 3 Asaconsequenceofthisproblemfollowsthecombinatorialproblemoffindingthecardinalityof 0 thefactorsetM =M/∼ consistingofallequivalenceclassesofM withrespectof∼. . Weassumfethatforeveryx ∈ M,thereisaprocedureK(x)whichreceivesallelementsofM, 1 0 whichareequivalenttox. 6 SinceM isafiniteset,thenthereexistsbijectivemapping 1 b :↔{1,2,...,|M|}, : v i whichwillcallnumberingfunction. Thus,eachelementofM uniquelycorrespondstoanelementof X BooleanarrayH[]withsizeequaltothecardinality|M|ofthesetM. Moreover,theelementx∈M r isselected ifH[b(x)]=1andxisnotselected ifH[b(x)]=0. a Thenextalgorithmisamodificationofthewell-knownmethod,knownas”SieveofEratosthenes” [Reingold,NievergeldandDeo(1977);YordzhevandMarkovska(2007)]solvesProblem1.1. Algorithm1.2. Receivesexactlyonerepresentativeofeachequivalenceclassofthefactor-setM = M/∼. f Input:FinitesetM Output: SetN ⊆M 1. N :=∅; E-mail:[email protected] 1 2. Declare a Boolean array H[ ] with size equal to the cardinality |M| of the set M and put H[b(x)]:=0forallx∈M; 3. Foreveryx∈M suchthatH[b(x)]=0do {Beginofloop1 4. N :=N∪{x}; 5. H[b(x)]:=1; 6. UsingtheprocedureK(x)obtainthesetP ={y∈M |y∼x}; x 7. Foreveryy∈P obtainedinstep6do x {Beginofloop2 8. H[b(y)]:=1; Endofloop2} Endofloop1} 9. Endofthealgorithm. Algorithm 1.2 has a number of disadvantages, the main of which is that it is practically inap- plicable for programs when a sufficiently great number of elements is present in the base set M. Thislimitationcomesfromthemaximuminteger,whichcanbeusedinthecorrespondingprogram- ming environment. For example, by standard in the C++ languagethe biggest number of the type unsignedlongint isequalto 232 −1, which ina numberof cases isinsufficientfor thepreviously definedarrayH[]tobecompletelyaddressed.Thepurposeofthisarticleistoavoidthisproblemby usingamultidimensionalBooleanarray,theelementsofwhichhaveaone-to-onecorrespondenceto theelementsofthebaseset,withamuchsmallerrangeoftheindices. Therearemanypublications relatedtomultidimensionalarrays,forexample[Mishra(2014)],buttheyarenotusedforourspecific goalsandobjectives. Anothersolutiontotheproblemistheuseofdynamicdatastructuresorother specialprogrammingtechniques[Collins(2002); Sutter (2002); Tan,SteebandHardy(2001)] butit isnotthesubjectofconsiderationinthisarticle. Binary(orBoolean,or(0,1)-matrix)isamatrixwhoseelementsareequalto0or1. LetBm×n bethesetofallm×nbinarymatrices. Itiswellknownthat |Bm×n|=2mn (1.1) Inthiswork,wewillconsiderandsolvethefollowingspecialcaseofProblem1.1: Problem1.3. LetBm×n bethesetofallm×nbinarymatricesandletX,Y ∈Bm×n. Wedefinean equivalencerelationρasfollows:XρY ifandonlyifwecanobtainX fromY byasequentialmoving ofthelastroworcolumntothefirstplace.Findthecardinality|Bm×n/ρ|ofthefactor-setM =Bm×n/ρ andreceiveasinglerepresentativeofeachequivalenceclass. f Theproofthatρisanequivalencerelationistrivialandwewillomitithere. The equivalenceclasses of Bm×n by theequivalencerelationρ area particularkind of double coset [Bogopolski (2008); CurtisandRainer (1962); DeVos (2010)]. They make use of substitu- tionsgrouptheoryandlinearrepresentationoffinitegrouptheory[CurtisandRainer(1962);DeVos (2010)]. When m = n, the elementsof the factor-setM = Bn×n/ρ put carry into practice in the textile technology[Borzunov(1983);YordzhevandKostadfinova(2012)]. In[Yordzhev(2005)]analgorithmisshown,whichutilizestheoreticalgraphicalmethodsforfind- ingthefactorsetS =Sn/ρ,whereSn ⊂Bn×nisasetofallpermutationmatrices,i.e.binarymatrices havingexactlyonee1oneachrowandeachcolumn. In[Yordzhev(2014)]weextendedthisproblem inthecasewhenρisanarbitrarypermutation. 2 Theauthorofthispaperisnotfamiliarwithanexistingageneralformulaexpressedasafunction ofmandnforfinding|Bm×n/ρ|. Thegoalofthispaperistodescribeaneffectivealgorithmforfinding thenumberofelementsofthefactorsetM = Bm×n/ρ,aswellasfindingasinglerepresentativeof eachequivalenceclass.Herewewilldescfribeanalgorithm,whichovercomessomedifficulties,which wouldinevitablyarisewithsufficientlygreatmandnifweapplytheclassicalalgorithm(Algorithm1.2). ThemaindifficultyarisesfromthegreatnumberofelementsofM =Bm×n/ρwithcomparativelysmall integersmandn,accordingtoformula(1.1). f Forundefinednotionsanddefinitions,wereferto[Aigner(1979);Sachkovand.Tarakanov(2002)]. 2 Description of an algorithm with the use of a multidi- mensional array Theorem2.1. LetusdenotebyP theset n P ={0,1,...,2n−1} (2.1) n Thenaone-to-onecorrespondence(bijection)betweentheelementsoftheCartesianproductPm= n Pn×Pn×···×PnandtheelementsofthesetBm×n ofallm×nbinarymatricesexists. | {mz } Proof. We consider the mapping α : Pnm → Bm×n, defined in the following way: If π ∈ Pnm and π =< p1,p2,...,pm > then let us denote by zi, i = 1,2,...,m, the representationof the integer p in a binary notation, and if less than n digits 0 or 1 are necessary, we fill z from the left with i i insignificant zeros, so that z will be written with exactly n digits. Since by definition, p ∈ P , i.e. i i n 0≤p ≤ 2n−1,thiswillalwaysbepossible. Thenweformanm×nbinarymatrix,sothatthei-th i rowiszi,i=1,2,...m. ApparentlythisisacorrectlydefinedmappingofPnmtoBm×n. Itisclearthat fordifferentn-tuplesfromPnm withthehelpofαwewillobtaindifferentmatricesfromBm×n,i.e. αis aninjection. Conversely,rowsofeachbinarymatrixcanbeconsideredasnaturalnumbers,written inbinarysystembyusingexactlyndigits0or1,eventuallywithinsignificantzerosinthebeginning, thatis,thesenumbersbelongtothesetP ={0,1,...,2n−1}. Thereforeeachm×nBinarymatrix n correspondstoanm-tupleofnumbers<p1,p2,...,pm >∈Pmn,thatis,αisasurjection. Henceαis abijection. It is easytosee the validityof thefollowingstatement, whichin factshowsthe meaningof our considerations. Proposition2.1. Letusdenotebyµthemaximuminteger,whichweusewhencodingtheelements ofthesetBm×nbymeansofthebijection,definedinTheorem2.1. Then,forsufficientlygreatmand n,thefollowingisvalid: µ=max(2n−1,m)≪|Bm×n|=2mn (2.2) Proof. Trivial. Let a andb be integers,b 6= 0. Witha/b we willdenotetheoperation”integerdivision”of a by b,i.e. ifthedivisionhasaremainder,thenthefractionalpartiscut,andwitha%bwewilldenotethe a q remainderwhendividingabyb. Inotherwords,if =p+ ,wherepandqareintegers,0≤q <b b b thenbydefinitiona/b=p,a%b=q. Weconsiderthefunction ξ(a)=(a%2)2n−1+a/2, (2.3) where%and/arethedefinedintheaboveoperations. 3 Definition 2.1. Let α be the defined in the proof of Theorem 2.1 bijection and let the functions fr,fc :Pnm →Pnmbedefinedsuchthatforeveryπ=<p1,p2,...,pm >∈Pnm fr(π)=<pm,p1,p2,...pm−1 > (2.4) fc(π)=<ξ(p1),ξ(p2),...,ξ(pm)>, (2.5) wherethefunctionξ(a)isthedefinedwith(2.3). Theorem2.2. LetA∈Bm×nbeanarbitrarym×nbinarymatrixandletαbethedefinedintheproof ofTheorem2.1bijection.Letustogetthematrices B=α f α−1(A) (2.6) (cid:0) r(cid:0) (cid:1)(cid:1) and C =α f α−1(A) (2.7) c (cid:0) (cid:0) (cid:1)(cid:1) ThenBisobtainedfromAbymovingthelastrowtothefirstplace,andC isobtainedfromAby movingthelast columntothe first place(respectivelythefirst rowor columnbecomesthesecond, thesecondbecomesthethirdrespectivelyetc.). Proof. Let π =< p1,p2,...,pm >= α−1(A) ∈ Pnm. Then the integer pi, 0 ≤ pi ≤ 2n −1, i = 1,2,...,m will correspondto the i-th row of the matrix A. Thenobviously, the matrixB = α(f (< r p1,p2,...,pm >)) = α(< pm,p1,p2,...,pm−1 >) is obtainedfromA bymovingthelast row inthe placeofthefirstone,andmovingtheremainingrowsonerowbelow. Let p ∈ P = {0,1,...,2n−1}, i = 1,2,...,m. Then d = p %2 gives the last digit of the i n i i binarynotationof the integerp . If p is writtenin binarynotationwith preciselyn digits, optionally i i with insignificantzeros in the beginning,then byapplyingintegerdivisionof p by 2, we practically i remove the last digit d and we move it to the first position, in case we multiply by 2n−1 and add i it to p /2. This is, by definition, how the function ξ(p ) works. Hence, the m× n binary matrix i i C = α(fc(< p1,p2,...,pm >)) = α(< ξ(p1),ξ(p2),...,ξ(pm) >))isobtainedfromthematrixAby movingthelastcolumntothefirstposition,andalltheothercolumnsaremovedonecolumntothe right. Fromthedefinitionsofthefunctionsf ,accordingto(2.4)andf ,accordingto(2.5)itiseasyto r c verifythevalidityofthefollowing Proposition2.2. Ifbydefinition 0 0 f (π)=f (π)=π (2.8) r c fk(π)=f fk−1(π) (2.9) r r(cid:16) r (cid:17) fk(π)=f fk−1(π) , (2.10) c c(cid:16) c (cid:17) whereπ∈Pmandkisapositiveinteger,then n fm(π)=π (2.11) r and fn(π)=π. (2.12) c Proof. Trivial. As a direct consequenceof Theorem2.1, Theorem2.2, Proposition2.2 and their constructive proofs, it follows that the following algorithm that finds exactly one representative of each equiva- lenceclasswithrespecttothedefinedinProblem1.3equivalencerelationρandthatcalculatesthe cardinalityofthefactorsetBm×n/ρ. 4 Algorithm2.3. Receivesexactlyonerepresentativeofeachequivalenceclassofthefactor-setM = M andcalculatesthecardinalityofthefactorsetM =M whenmandnaregiven. f /ρ /ρ f 1. Wedeclarethem-dimensionalBooleanarraysW1andW2whichwewillbeindexedbyusing the elements of the set Pnm, i.e. W1[< p1,p2,...,pm >] will correspond to the element < p1,p2,...,pm >∈Pnm. WeproceedanalogicallywiththearrayW2. 2. Initiallywe take all elementsof W1 and W2 to be 0. In W1 we will remember all elements selectedfromBm×n (oneforeachequivalenceclass)bychangingW1[<p1,p2,...,pm >]to 1ifwehaveselectedtheelementα(<p1,p2,...,pm >)forarepresentativeoftherespective equivalenceclass. WewillchangetheelementsofW2to1foreachselectionofanelement from Bm×n, i.e. for each π′′ ∈ Pnm, for which there exists π′ ∈ Pnm, such that W1[π′] = 1 and α(π′′)ρα(π′), or in other words, π′ and π′′ encode two different matrices of the same equivalenceclassaswehavechosenα(π′)forarepresentativeofthisequivalenceclass. 3. WedeclarethecounterN,whichweinitializeby0. Incaseofnormalendingofthealgorithm, N willbeshowingthecardinalityofthefactorsetBm×n/ρ. 4. Whileazeroelementexistsin W2do {Beginofloop1 5. Wechoose the minimalπ =< p1,π2,...,πm >∈ Pnm accordingto the lexicographic order,forwhichW1[π]=0. 6. W1[π]:=1; 7. N :=N+1; 8. Fori=1,2,...,mdo {Beginofloop2 9. π=fi(π). r 10. Forj =1,2,...,,ndo {Beginofloop3 11. π:=fj(π); c 12. W2[π]:=1; Endofloop3} Endofloop2} Endofloop1} 13. Endofthealgorithm. 3 CONCLUSIONS Applyingtheaboveideas,acomputerprogramthatreceivesacomputerprogramthatgetsonlyone representativefromeachequivalenceclassofthefactor-setBn×n =Bn×n/ρ. Thepurposeofthese calculationswastodescribeandclassifysometextilestructurees[YordzhevandKostadinova(2012)]. Theresultsrelatetoobtainingquantitativeestimationofallkindsoftextilefabric. In fact, the cardinalityof the factor-set M coincideswith an integersequence notedin On-Line EncyclopediaofIntegerSequences[Encyclopedia(2015)]asnumberA179043,namely A179043={2,7,64,4156,1342208,1908897152,11488774559744,288230376353050816, 29850020237398264483840,12676506002282327791964489728, 21970710674130840874443091905462272,154866286100907105149651981766316633972736, ... } 5 References Aigner,M.(1979)CombinatorialTheory.Springer-Verlag. Borzunov,C.W.(1983)ThextileIndustry-surveyInformation.v.3.Moscow:CNIIITEILP,.(inRussian) Bogopolski,O(2008)IntroductiontoGroupTheory.Zurich:EuropeanMathematicalSociety. Collins,W.J.(2002)Datastructuresandthestandardtemplatelibrary.McGraw-Hill. Curtis, C. W. and Rainer, I.(1962, 2006) Representation Theory of Finite Groups and Associative Algebras.NewYork: Wiley-Interscience. De Vos, A. (2010) Reversible Computing - Fundamentals, Quantum Computing, and Applications. Wiley. Mishra,P.(2014)ANewAlgorithmforUpdatingandQueryingSub-arraysofMultidimensionalArrays. arXiv: 1311.6093. Reingold,E.M., Nievergeld, J. and Deo N. (1977) Combinatorialalgorithms– Theoryand practice. PrenticeHall. Sutter,H.(2002)ExeptionalC++,Addison-Wesley. V.N.Sachkovand.Tarakanov,V.E(2002)CombinatoricsofNonnegativeMatrices,Amer.Math.Soc. TanKiatShi,SteebW.-H.andHardyY.(2001)SymbolicC++: AnIntroductiontoComputerAlgebra usingObject-OrientedProgramming.Springer. Yordzhev, K. (2005)On an equivalencerelationin the set of the permutationmatrices.in: Discrete MathematicsandApplications,SWUBlagoevgrad(BG)andUniversityofPotsdam(GER):pp77– 87. Yordzhev,K.(2014)Onthecardinalityofafactorsetinthesymmetricgroup.Asian-EuropeanJournal ofMathematics,Vol.7,No.21450027(14pages),DOI:10.1142/S1793557114500272 Yordzhev, K. and Kostadinova H. (2012) Mathematical Modelling in the Textile Industry. Bulletin of MathematicalSciences&Applications,Vol.1,No.1,pp.20-35. Yordzhev,K.andMarkovska,A.(2007)MethodoftheMultidimensionalSieveinthePracticalRealiza- tionofsomeCombinatorialAlgorithms.ProceedingsofInt.Sc.Conf.UNITECH07,23.11–24.11. 2007,Gabrovo,Bulgaria,Vol.II,pp.451–456. On-Line Encyclopedia of Integer Sequences (2015). A179043–Number of n × n checkered tori, http://oeis.org/A179043.(Lastaccessedon15Jan2016) 6