## Re: [PBML] enumerating all possible combinations of pairs

Expand Messages
• Order is an issue, but formatting is not. If all formatting is dropped, then your combinations would be: 1 2 1 3 1 4 2 3 2 4 3 4 But my desired output is: 1 2
Message 1 of 6 , Jun 7, 2007
Order is an issue, but formatting is not.
If all formatting is dropped, then your combinations would be:
1 2
1 3
1 4
2 3
2 4
3 4

But my desired output is:
1 2 3 4
1 3 2 4
1 4 2 3

All numbers are in each combination, with '1' always at first position.

kapil v <aaaaax2003@...> wrote: I really don't ger what you are saying. The combinations I generated are what you asked for. Is the order and formatting of the output that is the issue ?

Secondly,

@Randal
'combine' does not do what I want, and I didn't understand the code enough to modify it. I need to find combinations of 1, 2, 3, 4 such that
combination 1: 1-2, 3-4
combination 2: 1-3, 2-4
combination 3: 1-4, 2-3
where a-b => a pairs with b.
This problem is Depth first search with backtracking, and my code isn't backtracking the right way. I searched for already available codes for this problem, and I found some pseudocodes, but that didn't help.
Maybe I need to search more.

@Kapil
The code you wrote gives the following output (for 1, 2, 3, 4)
1,2
1,3
1,4
2,3
2,4
3,4
This is again a list of combinations different from what I have to generate.

I'm working on code, as well as searching for an already existing one. Any suggestions on where to search are most welcome.

Thanks!

kapil v <aaaaax2003@...> wrote: A simple solution
#/usr/bin/perl -w
my @array=(1,2,3,4,5,6,7);
combinations(\@array);
sub combinations{
my \$array_ref=shift;
my @array1 = @{\$array_ref};
\$size=@array1;
if(\$size<=1){return;}
\$first=\$array1[0];
for(\$i=1;\$i<\$size;\$i++){
print "\$first,\$array1[\$i]\n";
}
shift(@array1);
combinations(\@array1);
}
~

I have an array of numbers, and I have to enumerate all possible combinations of pairs, without repetition of numbers or pairs in a particular combination.

For example: if array is @list = (1, 2, 3, 4), then all possible combinations that could be generated are:
1-2, 3-4
1-3, 2-4
1-4, 2-3

For @list = (1, 2, 3, 4, 5, 6), there are 15 possible combinations.
1-2, 3-4, 5-6; 1-2, 3-5, 4-6; 1-2, 3-6, 4-5
1-3, 2-4, 5-6; 1-3, 2-5, 4-6; 1-3, 2-6, 4-5... and so on.

1 always stays at the first position.

I was trying to do this in a recursive manner using a subroutine (my first subroutine!). The @list is passed to it and result is stored in a 2D array (@stem_pair).

=====subroutine======

sub enumerate
{
#array of numbers passed to sub
my @list = @_;

\$flag = \$list[0];
for (my \$j = 1; \$j<scalar(@list); \$j++)
{
# to initialize output array using flag
# since \$flag = 1only during the 1st run of subroutine
if (\$flag == 1 ) # block executed only once
{
push @stem_pair, [ \$list[0], \$list[\$j] ];
# @first_pair: 1D array to keep track of pairs
@first_pair = (\$list[0], \$list[\$j] );
}

elsif (scalar(@list) > 2) # if more than one pair remain in list
{
push @first_pair ,\$list[0];
push @first_pair ,\$list[\$j];
# adding more pairs to the same row of @stem_pair
push @{ \$stem_pair[\$#stem_pair] }, \$list[0], \$list[\$j];
}
else # for last pair in the list
{
# adding more pairs to the same row of @stem_pair
push @{ \$stem_pair[\$#stem_pair] }, \$list[0], \$list[\$j];
}

@temp = @list;
# setting the zero value for elements just added to @stem_pair
\$temp[\$j] = 0;
\$temp[0] = 0;
# sorting array to get the two zeros as 1st and 2nd elements in array
@new = sort(@temp);
# deleting the two array elements
\$a = shift(@new);
\$a = shift(@new);
print "Remaining array is @new, element deleted was \$a\n";

# if no pairs are left
if (scalar(@new) < 2){
for (my \$k=0; \$k < \$j; \$k++) # remove pairs from @first_pair
{
\$b = pop(@first_pair);
\$b = pop(@first_pair);
}
# initialize new row in @stem_pair
push @stem_pair, [ @first_pair];
}
# else, call the function with this new array @new
else {enumerate(@new);}
}

}

======END======

The code works fine for @list= (1,2, 3, 4)

but gives extra repeated numbers for any list having more numbers.
For @list = (1,2, 3, 4, 5, 6)
output:

1-2, 3-4, 5-6
1-2, 3-5, 4-6
1-2. 3-6., 4-5
1-2, 1-3, 2-4, 5-6 ### 1-2 should have been deleted before adding 1-3
### but my attempts to include more pop commands deleted
### 1-3 as well
1-2, 1-3, 2-5, 4-6
1-2, 1-3, 2-6, 4-5
1-2, 1-3, 1-4, 2-3, 5-6
1-2, 1-3, 1-4, 2-5, 3-6
1-2, 1-3, 1-4, 2-6, 3-5
1-2, 1-3, 1-4, 1-5, 2-3, 4-6
1-2, 1-3, 1-4, 1-5, 2-4, 3-6
1-2, 1-3, 1-4, 1-5, 2-6, 3-4
1-2, 1-3, 1-4, 1-5, 1-6, 2-3, 4-5
1-2, 1-3, 1-4, 1-5, 1-6, 2-4, 3-5
1-2, 1-3, 1-4, 1-5, 1-6, 2-5, 3-4
1-2, 1-3, 1-4, 1-5, 1-6 ### this is the final @first_pair
### seen here as an extra 16th row

I've tried several things, but either am having less pairs (some pairs absent) or more pairs (some repetitions).
I would greatly appreciate any help / comments / suggestions.

Thank You!

---------------------------------
Looking for people who are YOUR TYPE? Find them here!

[Non-text portions of this message have been removed]

I know Karate, Kung fu and 47 other dangerous words.

---------------------------------
Yahoo! Mail is the world's favourite email. Don't settle for less, sign up for your freeaccount today.

[Non-text portions of this message have been removed]

---------------------------------

[Non-text portions of this message have been removed]

I know Karate, Kung fu and 47 other dangerous words.

---------------------------------
Now you can scan emails quickly with a reading pane. Get the new Yahoo! Mail.

[Non-text portions of this message have been removed]

---------------------------------