topic Get a full list of possible combinations of an asymmetric tree in SAS Programming

Get a full list of possible combinations of an asymmetric tree

user24feb — Wed, 08 Oct 2014 15:01:33 GMT

Hello,

I would like to get a full list of possible combinations af an asymmetric tree (which I think is the most general description of my problem).

In my particular case, I am dealing with different recipies to produce certain products, this is the same product can be made combining various, but descrete sets of components. For example, bill-of-materials alternative #1 says that product 200 0000 can be made either of 40 % material 400 0000 and 60 % intermediate product 4600000. Product 200 0000 could be made as well with 40 % raw material 4000009 and 60 % intermediate product 4600000 <- this is alternative #2, and so on.

* this is a list of potential bill-of-materials, actually there could be many final more products like 200 0000;
Data ProductStructure;
Input @1 Parent $7. @9 Component $7. @17 Alternative $2. Percentage_Quantity;
Datalines;
2000000 4000000 01 0.4
2000000 4600000 01 0.6
2000000 4000009 02 0.4
2000000 4600000 02 0.6
2000000 4000000 03 0.3
2000000 4600000 03 0.7
4600000 4500000 01 1
4600000 4500000 02 0.8
4600000 4500001 02 0.2
4600000 4500001 03 0.5
4600000 4500004 03 0.5
;
Run;

* the goal is a complete list, this is a "permutation", of all possible BoM-combinations;
/*
BoM #1:
2000000 4000000 01 0.4 -> alternative 01 of 2000000 consists of 0.4 units 4000000
2000000 4600000 01 0.6 -> alternative 01 of 2000000 consists of 0.6 units 4600000
4600000 4500000 01 1 -> alternative 01 of 4600000 (!!) consists of 1 unit 4500000

BoM #2:
2000000 4000000 01 0.4 -> alternative 01 of 2000000 consists of 0.4 units 4000000
2000000 4600000 01 0.6 -> alternative 01 of 2000000 consists of 0.6 units 4600000
4600000 4500000 02 0.8 -> alternative 02 of 4600000 (!!) consists of 0.8 units 4500000
4600000 4500001 02 0.2 -> alternative 02 of 4600000 (!! )consists of 0.2 units 4500001

BoM #3:
2000000 4000000 01 0.4
2000000 4600000 01 0.6
4600000 4500001 03 0.5
4600000 4500004 03 0.5

BoM #x:
2000000 4000000 03 0.3
2000000 4600000 03 0.7
4600000 4500001 03 0.5
4600000 4500004 03 0.5

My current approach would be to carry out a couple of merges to get to the wanted result. My question is, if there is a better/quicker way - in the best case a standard SAS-function (Proc BOM will only work for single product-component relationships) - to achieve this result.

Thanks&kind regards

Re: Get a full list of possible combinations of an asymmetric tree

stat_sas — Wed, 08 Oct 2014 15:20:18 GMT

proc sql;

create table want as

select * from ProductStructure,ProductStructure(rename=(parent=_parent component=_component

Alternative=_Alternative Percentage_Quantity=_Percentage_Quantity));

quit;

Re: Get a full list of possible combinations of an asymmetric tree

user24feb — Thu, 09 Oct 2014 08:30:34 GMT

Hi! I'm afraid it's a bit more complicated. The desired dataset is:

Product Component Quantity BoM_ID

2000000 4000000 0.4 2000000_01_4600000_01

2000000 4500000 0.6 2000000_01_4600000_01

2000000 4000000 0.4 2000000_01_4600000_02

2000000 4500000 0.48 2000000_01_4600000_02

2000000 4500001 0.12 2000000_01_4600000_02

2000000 4000000 0.4 2000000_01_4600000_03

2000000 4500001 0.3 2000000_01_4600000_03

2000000 4500004 0.3 2000000_01_4600000_03

2000000 4000009 0.4 2000000_02_4600000_01

2000000 4500000 0.6 2000000_02_4600000_01

2000000 4000009 0.4 2000000_02_4600000_02

2000000 4500000 0.48 2000000_02_4600000_02

2000000 4500001 0.12 2000000_02_4600000_02

2000000 4000009 0.4 2000000_02_4600000_03

2000000 4500001 0.3 2000000_02_4600000_03

2000000 4500004 0.3 2000000_02_4600000_03

2000000 4000000 0.3 2000000_03_4600000_01

2000000 4500000 0.7 2000000_03_4600000_01

2000000 4000000 0.3 2000000_03_4600000_02

2000000 4500000 0.56 2000000_03_4600000_02

2000000 4500001 0.14 2000000_03_4600000_02

2000000 4000000 0.3 2000000_03_4600000_03

2000000 4500001 0.35 2000000_03_4600000_03

2000000 4500004 0.35 2000000_03_4600000_03

The code - which unfortunately has its limitations - that gets me there is in the attached files.

Re: Get a full list of possible combinations of an asymmetric tree

Loko — Thu, 09 Oct 2014 13:15:19 GMT

Hello,

This works only if one component belongs to one parent.

Data ProductStructure;
Input @1 Parent $7. @9 Component $7. @17 Alternative $2. Percentage_Quantity;
dummy=Parent!!"_"!!Component!!"_"!!Alternative;
Datalines;
2000000 4000000 01 0.4
2000000 4600000 01 0.6
2000000 4000009 02 0.4
2000000 4600000 02 0.6
2000000 4000000 03 0.3
2000000 4600000 03 0.7
4600000 4500000 01 1
4600000 4500000 02 0.8
4600000 4500001 02 0.2
4600000 4500001 03 0.5
4600000 4500004 03 0.5
3000000 4000000 01 0.5
3000000 4700000 01 0.5
3000000 4000009 02 0.6
3000000 4700000 02 0.4
4700000 4500000 01 1
4700000 4500000 02 0.8
4700000 4500001 02 0.2
;
Run;

proc sql;
create table int as (
select x.parent, coalesce(y.inicomp, x.component) as component,x.alternative, coalesce(Percentage_Quantity*iniperc,x.Percentage_Quantity) as percent, x.component as subcomp
from ProductStructure (drop=dummy) x
left join
(
select b.parent as inipar,b.component as inicomp, b.alternative as inialt, b.Percentage_Quantity as iniperc
from ProductStructure a , ProductStructure b
where a.component=b.parent and a.alternative=b.alternative) y
on x.component=y.inipar

where x.parent not in
(select b.parent
from ProductStructure a , ProductStructure b
where a.component=b.parent and a.alternative=b.alternative))
order by parent, alternative, inialt
;
quit;

data want;
retain Perc_Ini Comp_Ini Perc_Ini ;*keep initial values;

set int;
by parent alternative;*data already from sorted from the sql syntax;

BoM_ID=catx("_",parent,alternative,subcomp,alternative);

output;*write the current record to data set;
percsum+percent;

if first.alternative then /*set initial values;*/
do;
Comp_Ini=component;
Perc_Ini=percent;
percsum=Perc_Ini;
end;

if round(percsum,0.1)=1 and not last.alternative then /*write a second line to data set if sum of percents is 1 and not the last record within group*/
do;
component=Comp_Ini;
percent=Perc_Ini;
output;
percsum=Perc_Ini;
end;

drop Perc_Ini Comp_Ini Perc_Ini percsum subcomp;
run;

Re: Get a full list of possible combinations of an asymmetric tree

Ksharp — Thu, 09 Oct 2014 14:00:38 GMT

Is there just two Prouct (Parent) ?

Data ProductStructure;
  Input @1 Parent $7. @9 Component $7. @17 Alternative $2. Percentage_Quantity;
  Datalines;
2000000 4000000 01 0.4
2000000 4600000 01 0.6
2000000 4000009 02 0.4
2000000 4600000 02 0.6
2000000 4000000 03 0.3
2000000 4600000 03 0.7
4600000 4500000 01 1
4600000 4500000 02 0.8
4600000 4500001 02 0.2
4600000 4500001 03 0.5
4600000 4500004 03 0.5
  ;
Run;
proc sort data=ProductStructure(keep=Parent Alternative) out=temp nodupkey; by Parent Alternative ;run;
data key(drop= n);
 set temp end=last nobs=nobs;
 retain n;
 if parent ne lag(parent) then n=_n_;
 if last then do;
  do i=1 to n-1;
   do j=n to nobs;
    bom+1;
    set temp point=i; output;
    set temp point=j; output;
   end;
  end;
end;
run;
data want(drop=rc);
 if _n_ eq 1 then do;
  if 0 then set ProductStructure;
  declare hash ha(dataset:'ProductStructure',multidata:'y');
   ha.definekey('Parent', 'Alternative');
   ha.definedata(all:'y');
   ha.definedone();
end;
set key;
rc=ha.find();
do while(rc=0);
 output;
 rc=ha.find_next();
end;
run;

Xia Keshan

Re: Get a full list of possible combinations of an asymmetric tree

user24feb — Thu, 09 Oct 2014 16:23:56 GMT

Wow.

You know a lot more than me and I am afraid I don't fully understand what the hash-part of the program does. Could you please explain?

data want(drop=rc);

if _n_ eq 1 then do;

if 0 then set ProductStructure; * what is eqal to 0 ?;

declare hash ha(dataset:'ProductStructure',multidata:'y'); * allow multiple observations;

ha.definekey('Parent', 'Alternative'); * why 2 keys?;

ha.definedata(all:'y'); * ?;

ha.definedone();

end;

set key;

rc=ha.find();

do while(rc=0); * why if 0 - zero means nothing was found;

output;

rc=ha.find_next();

end;

run;

Re: Get a full list of possible combinations of an asymmetric tree

Ksharp — Fri, 10 Oct 2014 11:57:02 GMT

That is just simply pick up the corresponding Obs from dataset ProductStructure ,according to the key(Parent and Alternative) value of dataset KEY .

" * what is eqal to 0 ?;"

It is just to initial the variable which used for Hash Table , otherwise you can't build a Hash Table .

"* why 2 keys?;"

The reason is I make all of combination based on these two variables.

"ha.definedata(all:'y'); * ?;"

Include all of variable in dataset ProductStructure be the DATA field of Hash Table.

" * why if 0 - zero means nothing was found;"

Means if I find one (=0), I will continue to find next (rc=ha.find_next();) .

Xia Keshan

Re: Get a full list of possible combinations of an asymmetric tree

gergely_batho — Mon, 13 Oct 2014 09:53:00 GMT

Hi,

attached is a program, that has no restrictions on the product sturcture (Of course do avoid cycles! ).

Sorry, it is not very well documented, and maybe it is easyer to write this program, than to understand.

Important:

You will need one additional pass through the results, because if a component is included on multiple products paths, it will appeare multiple times in the result. (You have no such cases in the attached product stucture.) I think you can easily aggregate them. (I didn't want to complicate this program any further.)

Also in my program BOM_id is simply a number. If you have multiple levels in the product tree, it makes no more sense to include this info in an ID field. Is it? Anyway, you can consturct a (very long) character variable that can include the "path" of the product decomposition.

Look at this formula in my program: bom_quant*Percentage_Quantity Similarly you can constuct a variable like this: bom_path || Parent || Alternative

I have changed your input data a bit: I included more levels.

Currently this program reads a dataset called Parts. The program could be easily exteded to handle more parts, but right now it expands only 1 row (=1 Part).

Be carefull with big product trees. The result can become quickly huge. (I guess you know that.)

Algorithm:

We maintain a list of BOMs in an internal table (bom_list). We initialize this table with one row: the unexpanded part list (unexpanded BOM).

We go through this list again and again and when we find a Part, that can be expanded (i.e. it is in the productStucture table as Parent), we expand it.

Expanding means simply copying all the entries (rows) of a BOM numAlternatives times. While copying, we keep all entries as they are, except the entry, that should be expanded. That entry is replaced and sometimes also doubled/tripled/etc., depenting how many Children (Components) the Parent has.

The rest is just technical (not algorithmical) thing: I am dynamically adding and removing from this internal (hash) table. I am using an iterator to "walk" through it. Also I am using some more hash tables, and iterators to make my life easier. See inline comments in the code.

Technically I don't re-read the bom_list table, I am reading it only once. But while reading I am appending new entries to the end of the list(table).

Re: Get a full list of possible combinations of an asymmetric tree

user24feb — Thu, 16 Oct 2014 06:34:44 GMT

Thanks Ksharp and Gergely Batho!! The Hash-idea is the key.

Re: Get a full list of possible combinations of an asymmetric tree

weigel_s — Mon, 13 Apr 2015 14:04:34 GMT

simple cartesian join with a wrapping select criteria?

select distinct * from

(

select

a.key, a.var1, a.var2...

b.key as b.key_, b.var1, b.var2

from table1 a, table2 b

)

where (a.key = b.key_);

provided you have enough space/memory/ etc. to do this all in one step?

or maybe it's not this simple?

Re: Get a full list of possible combinations of an asymmetric tree

user24feb — Tue, 14 Apr 2015 06:20:16 GMT

If I understood your program correctly, it is not what I was up to. In fact, my final code was very similar to Xia Keshan's (will set his answer to correct shortly). I hope the following code demonstrates, why I did not choose proc sql but a hash table:

Data A;
Input Prod Comp;
Datalines;
1 33
1 44
2 11
2 55
2 66
;

Data B;
Input Comp Subcomp;
Datalines;
33 111
33 222
55 666
55 777
55 888
;

Proc SQL;
Select A.Prod, A.Comp, B.Subcomp From A, B Where A.Comp eq B.Comp;
Quit;

Data Want (Drop=rc);
Length Comp 8. Subcomp 8.;
If _N_ eq 1 Then Do;
    Declare Hash H (Dataset:'B',Multidata:'y');
H.Definekey('Comp');
H.Definedata('Subcomp');
H.Definedone();
Call Missing (Comp, Subcomp);
End;
Do While (not Eof);
    Set A End=Eof;
    rc=H.Find();
If (rc) Then Do;
      Call Missing (Subcomp);
   Output;
End;
Do While (not rc);
      Output;
   rc=H.Find_next();
End;
End;
Run;
Proc Print Data=Want; Run;