BookmarkSubscribeRSS Feed
Hugo123
Calcite | Level 5

I am trying to simulate combinations based on 5 coordinates (datset below):

data coord;

input x 1. y 1.;

datalines;

11

32

55

91

14

run;

Every combination must begin with (1,1) and end with (1,1) i.e.

(1,1) -> (3,2)-> (5,5)-> (9,1)-> (1,4)-> (1,1)

and all combinations must be unique and finally that there can't be the above route and

(1,1) ->(1,4)-> (9,1)-> (5,5)-> (3,2)-> (1,1)

as both routes are the same but in opposite directions.

Is there a way to do this in sas?

3 REPLIES 3
FatCaptain
Fluorite | Level 6

The code below should do what you require.

 

Just a few notes.

 

1) I've stuck the x and the y coordinate together as it's easier to deal with them in this way.

2) I've hard coded the 1,1 coordinate as it does not change. This can however be incorporated into the data if you require.

3) The data set outds2 also contains a list of the routes you require and outds3 contains the reverse of these routes.

 

 

 

/*Set up the initial table*/
data coord;
input xy 8.;
datalines;
32
55
91
14
run;

/*Find all unique routes*/
proc sql noprint ;
create table outds as
select 11 as c1,
       a.xy as c2,
       b.xy as c3,
       c.xy as c4,
       d.xy as c5,
       11 as c6
from coord as a,
     coord as b,
     coord as c,
     coord as d
where a.xy ne b.xy and a.xy ne c.xy and a.xy ne d.xy and b.xy ne c.xy and b.xy ne d.xy and c.xy ne d.xy ;

select count(*) into :nobserv from outds ;

quit ;

/*Find the routes which are the reverse of already known routes*/
data outds2 (drop=c2_2 c3_2 c4_2 c5_2);
do i = 1 to &nobserv-1 ;
    do j = i+1 to &nobserv ;
        set outds point=i ;
            set outds (rename=(c2=c2_2 c3=c3_2 c4=c4_2 c5=c5_2)) point=j ;
                if c2=c5_2 and c3=c4_2 and c4=c3_2 and c5=c2_2 then output ;
    end ;
end ;
stop ;
run ;

/*Remove the reverse routes from the main data set*/
proc sql ;
create table outds3 as
select *
from   outds
except all
select *
from   outds2 ;
quit ;

MikeZdeb
Rhodochrosite | Level 12

Hi, here's another approach that uses LEXPERM to generate the permutations of nodes (same answer as the other posted solution with some paths shown in the reverse order) ...

 

* generate permutations of four nodes;
data perm;
array x(4) $2 ('32' '14' '55' '91');
do j=1 to fact(4);
   rc=lexperm(j, of x(*));
   output;
end;
keep x:;
run;

 

* identify duplicates (left-2-right = right-2-left, output only one of the pair);

data check;

retain x0 x5 '11';
set perm nobs=howmany;
s1 = catt(of x1-x4);
do j=_n_ to howmany;
   set perm point=j;
   s2 = catt(of x4-x1);
   if s1 eq s2 then leave;
end;
if s1 eq s2 then output;
keep x:;
run;

 

data set CHECK ...

Obs x0 x1 x2 x3 x4 x5

 1  11 91 55 32 14 11
 2  11 55 91 32 14 11
 3  11 91 32 55 14 11
 4  11 32 91 55 14 11
 5  11 55 32 91 14 11
 6  11 32 55 91 14 11
 7  11 91 55 14 32 11
 8  11 55 91 14 32 11
 9  11 91 14 55 32 11
10  11 55 14 91 32 11
11  11 91 32 14 55 11
12  11 91 14 32 55 11

 

 

Rick_SAS
SAS Super FREQ

This is an enumeration of the possible paths in the Traveling Salesman problem.  As the number of points grows, brute-force enumeration becomes prohibitive, but you can use various optimization schemes to obtain optimal or nearly optimal paths.

 

Do an internet search for +SAS "Traveling salesman" to see many solutions in SAS for the TSP.

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

How to Concatenate Values

Learn how use the CAT functions in SAS to join values from multiple variables into a single value.

Find more tutorials on the SAS Users YouTube channel.

Click image to register for webinarClick image to register for webinar

Classroom Training Available!

Select SAS Training centers are offering in-person courses. View upcoming courses for:

View all other training opportunities.

Discussion stats
  • 3 replies
  • 1033 views
  • 1 like
  • 4 in conversation