Loading ...
Sorry, an error occurred while loading the content.

Re: [PBML] enumerating all possible combinations of pairs

Expand Messages
  • aditi gupta
    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
    • 0 Attachment
      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 ?

      aditi gupta <aditi9783@...> wrote: Firstly, Thank you for replying.

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

      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);
      }
      ~

      aditi gupta <aditi9783@...> 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 $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!

      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]





      ---------------------------------
      Did you know? You can CHAT without downloading messenger. Know how!

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






      ---------------------------------
      Did you know? You can CHAT without downloading messenger. Know how!

      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.