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

 Page 1 of 1 [ 4 post ]

Relevant Pages

Powered by phpBB® Forum Software