topic Re: Combinatorial problem in SAS Programming

Combinatorial problem

PaigeMiller — Sun, 09 Aug 2020 19:45:41 GMT

I'm hoping someone can help me with this problem.

To start, I have 15 people, and I want to assign them randomly to groups of 3. No problem, I know how to do that.

The real problem is that I want to randomly assign each person to a second group of 3 with the restriction that none of my 15 people see the same individual in the second group of three as they saw in the first group of three. And then continue, assign each person randomly to a 3rd group of three, such that no person still has seen another person more than once. And so on, until each person is assigned to a 7th group such that each person has seen all of the other 14 people exactly once.

Can anyone point me in the right direction?

Re: Combinatorial problem

mkeintz — Sun, 09 Aug 2020 21:04:04 GMT

Now that's one to think about.

Re: Combinatorial problem

Astounding — Mon, 10 Aug 2020 01:43:56 GMT

Not sure this will help, but it's food for thought.

Would it help to create all 105 unique pairs, and use that as a starting point? For example:

randomly select which pairs to use (and remove those from the list of 105)
randomly select which third ID to add to each pair, taking care not to use anyone twice
repeat for the remaining 90 pairs

I'm not sure how to do all this but if it's a valid approach it may simplify things a bit.

Re: Combinatorial problem

andreas_lds — Mon, 10 Aug 2020 05:58:50 GMT

Is randomness really required in the first step? If, at the end, "each person has seen all of the other 14 people exactly once"?

Re: Combinatorial problem

PaigeMiller — Mon, 10 Aug 2020 10:37:23 GMT

@andreas_lds wrote:

Is randomness really required in the first step? If, at the end, "each person has seen all of the other 14 people exactly once"?

You are correct! Randomness is not required at all.

Re: Combinatorial problem

Shmuel — Mon, 10 Aug 2020 13:14:52 GMT

Next code creates 35 records each with 3 numbers in the range of 1 to 15.

I am not sure that in some cases it will not create duplicates.

Any how I ran it without dups.

/*
https://communities.sas.com/t5/SAS-Programming/Combinatorial-problem/m-p/675498
*/

data g3;
     array tx {15} t1-t15;   /* temporary */
     array sx {15} s1-s15;   /* sorted */
     array vx {105} v1-v105; /* 7 groups * 5 3rds * 3 digits */
    
    /* initiate */
    do i=1 to 15; vx(i) = i; end;
    
    /* add 6 groups of 3*5 */
    do j=1 to 6;  
       link init_tx;
       link select_rand; /* new random order of 1-15 */
       link apnd15_2vx;
       
    end;
    
    /* output in group of 3 */
    do i=1 to 105 by 3;
       if vx(i) = . then leave;
       comb = catx(',',put(vx(i),2.),put(vx(i+1),2.),put(vx(i+2),2.));
       keep i comb;
       output;
    end;
    
return;
*==========;
INIT_TX:
   do i=1 to 15; tx(i) = .; end;
return;
*==========;
SELECT_RAND:
   do i=1 to 15;
      flag=0;
      do until (flag=1);
          n = round(15*ranuni(0),1.); if n=0 then n+1;
          if not (whichn(n,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15)) > 0 then do;
             flag=1; tx(i) = n;
          end; 
      end;
   end;
return;
*==========;
APND15_2VX:
   do i=1 to 15;
      vx(j*15+i) = tx(i);
   end;
return;
*==========;

run;

proc sort data=g3 out=g3s nodupkey ; by comb; run;

Re: Combinatorial problem

FreelanceReinh — Mon, 10 Aug 2020 15:16:38 GMT

Hi @PaigeMiller,

I found one particular solution in

D.R. Cox, N. Reid (2000): The Theory of the Design of Experiments. Boca Raton: Chapman & Hall/CRC (see Table 4.4, p. 73).

It's an example of an incomplete block design. Many (if not all) other solutions could be derived from this by permuting the 15 IDs.

The page happens to be available via Google book search:

https://books.google.de/books?id=a_vKBQAAQBAJ&pg=PA72&dq=%22Two+special+incomplete+block+designs%22&hl=de&sa=X&ved=2ahUKEwi32Yek9ZDrAhXMzqQKHZuYDogQuwUwAHoECAAQCg#v=onepage&q=%22Two%20special%20incomplete%20block%20designs%22&f=false

Note that there's a typo in row IV, column four: The "4" must read "14"!

Re: Combinatorial problem

s_lassen — Mon, 10 Aug 2020 17:12:06 GMT

If randomness is not required, here is a (relatively) simple way to do it.

First, some test data:

data persons;
  do _N_=1 to 15;
    ID=213*_N_+33;
    output;
    end;
run;

Then generate all possible ordered triples of numbers from 1 to 15:

data all;
  do P1=1 to 13;
    do P2=P1+1 to 14;
      do P3=P2+1 to 15;
        output;
        end;
      end;
    end;
run;

Now, create an empty table to hold the pairs that have already been used:

data used;
  length _P1 _P2 8;
  stop;
run;

proc sql;
  create index idx on used(_P1,_P2);
quit;

And showtime! Create a list of 35 usable triples in table TRIPLES:

data triples(keep=P1 P2 P3) used;
  found=1;
  set all;
  _P1=P1;
  _P2=P2;
  link check;
  _P2=P3;
  link check;
  _P1=P2;
  link check;
  if found then do;
    output triples;
    _P1=P1;
    _P2=P2;
    output used;
    _P2=P3;
    output used;
    _P1=P2;
    output used;
    end;
  _error_=0;
  return;
  check:
    modify used key=idx;
    if _iorc_=0 then /* key was found, meaning pair has already been used */
      found=0;
    return;     
run;

Finally, get the actual person data:

data want;
  set triples;
  set persons(rename=(ID=ID1)) point=P1;
  set persons(rename=(ID=ID2)) point=P2;
  set persons(rename=(ID=ID3)) point=P3;
run;

If you do want random after all, you can sort the table PERSONS in random order before creating WANT. But do not sort ALL, that breaks the program.

Re: Combinatorial problem

PaigeMiller — Mon, 10 Aug 2020 19:18:48 GMT

Incomplete block designs ... why didn't I think of that?

Re: Combinatorial problem

PaigeMiller — Mon, 10 Aug 2020 19:27:23 GMT

@s_lassen this is brilliant, and I will have to study the code to be sure I understand it properly, but it does seem to work. Thanks! I could only mark one answer correct, and so the first one offered is the one I marked correct.

Re: Combinatorial problem

PaigeMiller — Mon, 10 Aug 2020 20:10:34 GMT

Okay, @s_lassen @FreelanceReinh and others

There's one more problem that isn't solved, and where the analogy to incomplete block designs breaks down. I have to schedule the 15 people into groups of 3 over 7 different time periods. The solutions presented so far provide the groups, such that no person is in the same group as any other person twice (or more). But how do I split these groups into 7 time periods now such that each of the 7 time periods has 5 of the groups and no person appears in a time period more than once?? How do I create a schedule, because as you know, a person cannot be in two groups at once.

Re: Combinatorial problem

PaigeMiller — Mon, 10 Aug 2020 22:42:18 GMT

I was able to use "brute force" to search for 5 groups of 3, repeating for 7 weeks, with no person seeing another person more than once, from the code provided above by @s_lassen . If there are smarter ways to do this that don't involve "brute force" searching through all possible combinations of groups, please let me know.

Re: Combinatorial problem

FreelanceReinh — Tue, 11 Aug 2020 12:07:43 GMT

@PaigeMiller wrote:

Okay, @s_lassen @FreelanceReinh and others

There's one more problem that isn't solved, and where the analogy to incomplete block designs breaks down. I have to schedule the 15 people into groups of 3 over 7 different time periods. The solutions presented so far provide the groups, such that no person is in the same group as any other person twice (or more). But how do I split these groups into 7 time periods now such that each of the 7 time periods has 5 of the groups and no person appears in a time period more than once?? How do I create a schedule, because as you know, a person cannot be in two groups at once.

Not sure if I understand the issue correctly. The book solution (with the typo corrected) does satisfy the condition that each of the 7 "time periods" (numbered I, II, III, ..., VII) contains each of the 15 "persons" exactly once (in addition to the criterion about persons meeting only once in a group). What is the new criterion that is not yet satisfied?

Re: Combinatorial problem

PaigeMiller — Tue, 11 Aug 2020 12:27:16 GMT

In an incomplete block design, I can have treatments 1, 2 and 3 in a group, and the very next group can be treatments 1,4,5, and so on, until all blocks are assigned and then the test can all be run at one time.

With people, I cannot have 1,2,3 together at the same time as I have 1,4,5 together. 1,2,3 has to be at a given time period, say time 1, and 1,4,5 cannot happen at time 1, it must happen at time 2 or later. So I must assign 5 groups at time 1, and another 5 groups at time 2, with the restriction that no individual gets assigned more than one time at a given time period.

Re: Combinatorial problem

FreelanceReinh — Tue, 11 Aug 2020 12:52:40 GMT

Sure. But, again, in the particular solution from the book I don't see such a conflict where one person (i.e., number 1, ..., 15) occurs twice in the same time period (i.e., row I, II, ..., VII).

Re: Combinatorial problem

PaigeMiller — Tue, 11 Aug 2020 13:30:07 GMT

Okay, I see your point. Obviously, the book has the answer. I was working from the code provided by @s_lassen which doesn't quite perform this last step. Thanks!