enumerating all possible combinations of pairs

Hello All:

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
# already added to stem_pair
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 $an";

# 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!

Aditi

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

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

Messages in this topic (1) Reply (via web post) | Start a new topic

.

>>&gt;>> "aditi" == aditi gupta < aditi9783%40yahoo.co.in">aditi9783yahoo.co.in> writes:

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

You want "combine" from Math::Combinatorics from the CPAN.
Stop writing common code yourself.

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<; merlyn%40stonehenge.com">merlynstonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!

Messages in this topic (0) Reply (via web post) | Start a new topic

.

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&lt;=1){return;}
$first=$array1[0];
for($i=1;$i<$size;$i++){
print "$first,$array1[$i]n";
}
shift(array1);
combinations(array1);
}
~

aditi gupta < aditi9783%40yahoo.co.in">aditi9783yahoo.co.in> wrote: Hello All:

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
# already added to stem_pair
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 $an";

# 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!

Aditi

---------------------------------
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]

Messages in this topic (0) Reply (via web post) | Start a new topic

.