NB. cutting materials problem NB. by Yamamoto Yoichi /Japla 2014/10/18 NB. -------------------------------- NB.***************************************************** NB. utuls-------------------------------- tap=: i.@! A. i. NB. Table of Permutations ts=: 6!:2 NB. time & space//Usage: ts 'a=. partition 30' NB. ------------------------------------- perm=: 4 : '(y ! x) * ! y' NB. permutiation combi=: 4 : 'y ! x ' NB. combination NB. partition numbers NB. ----find partition numbers with details----------------------- NB. written by Shimura Masato NB. is file includes in classes/calculus/numeric/partition_shimura.ijs partition=: 3 : 0 NB. partition number NB. Usage: e.g. partition 10 ANS=. (<<1),(<1 1;2) NB. 0,1 if. y<3 do. ANS=. ;("1),. ANS goto_skip. end. NR0=: }. >: i. y NB. first is 2 NB. ----------------------- for_ctr. i. <:# NR0 do. NB. number exam TMP2=. ((>:ctr) {. NR0) calc_part_sub ANS ANS=. ANS,< (: ctr { NR0 end. NB. ANS=. ; 10 #. L:0 |. {: ;("1),. ANS NB. change on 10 sin-suu ANS=. {: ;("1),. ANS NB. change on 10 sin-suu label_skip. ANS ) calc_part_sub=: 4 : 0 RW=. |. i. # NR=. x NB. RAW for pickup e.g. 5->2 3 4 ANS2=. <'' for_ctr. i. # NR do. NB. partial of number exam Y0=.(ctr{RW) { y if. 0=*/ (ctr{NR) check_major Y0 do. Y0=. ((ctr{NR) check_major Y0) # L:1 Y0 end. TMP1=. >(< ctr{NR) , L:0 Y0 NB. connect with , ANS2=. ANS2,:/ L:0 ; y ' NB. --------------------------------------------- NB. ************************************************************** NB. -------sub------------------------------- expand_box=: 4 : 0 NB. x is combi0 and y is combi1 ,. (({: $ y) # x ), L:0, y ) nCm=: 3 : 0 NB. calc table of n C m NB. nCm 5 3 <---> j form is 3 ! 5 'n0 m0'=. y ~. /:~"(1) m0{."1 tap n0 ) find_rest=: 4 : 0 NB. x is tmp1 NB. list is $ 1 4---> $ 4 NB. y is num (-. (i.y) e. x) # i.y ) NB. ---------------------------------- NB. stem include partition one after the bother NB. so resize partition resize_stem=: 4 : 0 NB. usage: 3 2 2 resize_stem 7 partorder=. \:~ x size=. y tmp0=. x part_combination y nonbox=:((# tmp0),y)$ ; tmp0 index=. ; -.@ * L:0 i. L:0 {@> partorder |: > { L:0 (''; index)<;.1 nonbox ) NB. set in type resize_stem_sub=: 4 : 0 tmp0=. y NB. ans nonbox=.((# tmp0),+/x)$ ; tmp0 index=. ; -.@ * L:0 i. L:0 {@> x NB. partorder |: > { L:0 (''; index)<;.1 nonbox ) NB. ---------------------------------- NB. ----find all--combination------------------------------ NB. semi automatic method part_combination=: 4 : 0 NB. x is using partition i.g. 4 3 1 NB. y is number of material ex. 8 NB. Usage: 3 1 1 part_combination 5 NB. - input x y--------------------------------------------- NB. i.g. 5 3 2 1 //is part of 10 partorder=: \:~ x NB. order(part) of partition(downsort) size =. y NB. size is fix NB. nnumber mnumber is n and m of nCm NB. check input------------------ NB. procedure part of bignumber bigpart=: +/ 2 <: partorder NB. number of not 1 nlist=: +/\. partorder NB. siffix 5 3 1 -> tane n NB. ---------------------------------------------------------- if. -. size = +/ partorder do. 'number-over' goto_end. end. NB. not equal if. 0= bigpart do. ans=. {@> i.y goto_end. end. NB. 1 1 1 1 1 NB. ---------------------------- ans=. <'' nnumber=: {. nlist NB. take n mnumber=: {. partorder NB. take m stem=: { combi0=: nCm nnumber , mnumber NB. ---procedure--big part---------------------------- for_ctr0. i. bigpart do. NB. loop within bignumber ctr=: ctr0 NB. ------skip loop case n=m------------------------------------- if. nnumber = mnumber do. ans=.ans, stem ,.stem find_rest (L:0) size goto_skip. end. NB. ---------------------------------------------------------- select. 0 < ctr0 NB. 1st or 2nd case. 0 do. remain =: ({combi0) find_rest (L:0) size case. 1 do. combi1=: nCm nnumber,mnumber stick=: >{ L:0 combi1 {L:0 remain stem=: stem expand_box stick remain =: stem find_rest (L:0) size end. nnumber=: (>:ctr0) { nlist NB. take n for next mnumber=: (>:ctr0) { partorder NB. take m for next end. ans=. ans,< stem,.stem find_rest (L:0) size NB. ---------procedure part 1 1 1...----------------- label_skip. if. 1 <: +/ partorder e. 1 do. NB. managing 1..1 tmp=. stem find_rest L:0 size if. 1< # > {.tmp do. tmp=.>{@> L:0 tmp end. NB. 1|1|1 ans=.stem ,. tmp end. NB. --------------------------- partorder resize_stem_sub }.ans NB. }. ans label_end. ) NB. ------------------------------------------ select_inner=: 4 : 0 NB. Usage: NB. goods=. 6500;4000 3000 2000 1000 500 NB. goods select_inner 4 1 part_combination 5 'material piece'=: x pindex=: y NB. m part_combination n cand=: pindex { L:0 piece tmp=: > material >: L:0 +/ L:0 cand select. +/ */"1 tmp case. 0 do. 'nothing in this partition ' fcase. do. (*/"1 tmp) # cand end. ) find_fitting=: 4 : 0 NB. Usage: (6500;4000 3000 2000 1000 500) find_fitting a 'material piece'=: x NB. y is result of a=. m part_combination y cand=. x select_inner y try. tmp1=: material - L:0 +/ L:0 cand catch. 'nothing in this partition' goto_end. end. cand,.tmp1,.{@>+/"1 > tmp1 label_end. ) NB. - below are not using sub-------------------------------------- NB. pickup combination pick_combi=: 4 : ' ~. /:~ ("0 1) y {."1 tap x ' NB. input nCm x is n and y is m find_restBox=: 4 : 0 NB. find_zan in each box NB. x is Combiinsie NB. y is num if.1= {.$ x do. tmp=. ,./ x else. tmp=. x end. NB. $1 4 --> $ 4 NB. (-. L:0 (i. y) e. L:0 { tmp) # L:0 i.y (-. L:0 (i.y) e. L:0 { tmp) # L:0 i.y ) check_over=: 4 : 0 NB. x is material and size NB. y is combi0 NB. Usage:(6500;size) check_over combi1 NB. over is null 'm s'=: x ( 0<: m- +/"1 y{s )# y )