all unique subsets of a list 
Author Message
 all unique subsets of a list

There's been lots of help with permutations of a list, but ...

can someone help with [Subj]?



I.e., if N=4 (for example), then the subsets would be:

(1,3,4,5),
(1,3,4,6),
(1,3,4,7),
....,
(2,3,7,8),
....,
(5,6,7,8)

The order of the elements is irrelevant; i.e.,

    (2,5,7,4) is "the same" as (5,7,4,2)

It seems to me that this last condition should reduce the computation
significantly, as compared to the permutation routine, yet I can't seem
to formulate the solution.

Apologies if this borders on off-topic (seems more of an abstractly
algorithmic problem, than strictly perl), but maybe someone knows of a
perl trick that I haven't included?

My clumsy routine uses recursing, sorting, splicing, and hash keys. It
processes all the redundant (in my definition) subsets (very slow!).

- ---- my lame code below:

sub Subset {


                # elements in the subsets

     # (the incrementation is to count redundancies)
     # the keys are the subsets- e.g., "1:3:7:8"
     return;
     # stop recursing when we get $N elements
  }


  foreach $i (0..$#_) {


  }

Quote:
}

---------------
after running

        $N=4; &Subsets(1..9);

(keys %results) is a list of "subsets" (stored as
':'-delimited strings)

Thanks in advance,

Andrew

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Wed, 18 Jun 1902 08:00:00 GMT  
 all unique subsets of a list


Quote:
> can someone help with [Subj]?




Here a small, quite dirty, hack that will do the trick (please don't
try to understand why I named my variables like I did).

#!/usr/bin/perl -w

use strict;



print "And here they are:\n";

sub permu
{


  return $selection unless $levels_left;



  {



  }


Quote:
}

__END__

--
                 map { print chr( $l += $_ ) } '
89+12+15-84+65+13+1+5-12-3+13-82+48+21+13-6-76+72-7+2+8-6+13-68==46
                     ' =~ /(-?\d+)(?=..)/g;



Wed, 18 Jun 1902 08:00:00 GMT  
 all unique subsets of a list

Quote:
> There's been lots of help with permutations of a list, but ...

> can someone help with [Subj]?

Two translations of Pascal algorithms from one of the old books on my
bookshelf:
Dietmar Herrmann, Algorithmen Arbeitsbuch, Addison-Wesley 1992

First a recursive one:

#!perl -w
use strict;

sub k_subsets_rec {




  my $next_k_subset;
  $next_k_subset = sub {

    for (my $i = $lo; $i <= $n - $k + $d; $i++) {
      $idx[$d] = $i;
      if ($d < $k-1) {
        &$next_k_subset($d + 1, $i + 1);
      } else {

      }
    }
  };
  &$next_k_subset(0,0);


Quote:
}





Quote:
}

__END__

And an iterative one:

#!perl -w
use strict;

sub binkoef {

  my $result = 1;
  for (my $i = 1; $i <= $k; $i++) {
    $result = $result * ($n - $i + 1) / $i;
  }

  return $result;

Quote:
}

sub k_subsets_iter {


  my $binkoef = binkoef($k, $n);


  my $next_k_subset;
  $next_k_subset = sub {
    my $i = $k-1;
    while ($idx[$i] == $n - $k + $i) {
      $i--;
    }
    $idx[$i]++;

    for (my $j = $i + 1; $j <= $k-1; $j++) {
      $idx[$j] = $idx[$j - 1] + 1
    }
  };

  for (my $i = 0; $i < $binkoef; $i++) {

    &$next_k_subset();
  }


Quote:
}





Quote:
}

__END__


Wed, 18 Jun 1902 08:00:00 GMT  
 all unique subsets of a list

Quote:




You mean to say ``combinations''.

Quote:
> I.e., if N=4 (for example), then the subsets would be:

> (1,3,4,5),
> (1,3,4,6),
> (1,3,4,7),
> ....,
> (2,3,7,8),
> ....,
> (5,6,7,8)

What you want is called a ``power set''. See this recent thread in
comp.lang.perl.misc for several good solutions:

    http://x30.deja.com/[ST_rn=ps]/viewthread.xp?AN=546557570

--
Jim Monty

Tempe, Arizona USA



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. generating a list of unique random codes

2. Assigning Directory Contents to a Unique List

3. fastest way to get a unique list

4. novice q: finding unique words in a list

5. novice q: finding unique words in a list

6. making unique list of words matching a pattern

7. need help making a unique array list

8. dir list of unique items

9. How to get unique list value

10. Reducing to a unique list of filenames

11. creating a list of unique records

12. fastest way to get a unique list

 

 
Powered by phpBB® Forum Software