in reply to Permutation seed generator

If I understand correctly, you want all the possible subsets of a set: 
my @set = qw|0 1 2 3|;

foreach my $index (0..2**@set-1) {
   my @subset;
   foreach my $pos (0..@set-1) {
      push @subset, $set[$pos] if ($index >> $pos) % 2;
   }
   print join " ", @subset, "\n";
}

[download]
Here, $index iterates over all members of the power set. This should work for sets up to 32 members in size for 32-bit integers.

-Mark

Replies are listed 'Best First'.
Re: Re: Permutation seed generator
by dimar (Curate) on May 06, 2004 at 15:17 UTC

    This does not answer your question, and it's not even a Perl suggestion, but I have to ask ...

    why use permutations *at all*?

    If the only requirement is to allow a user-definable ordering of known table fields, why not just give the user four 'select' boxes, one for each column?

    In other words, give the user four of these ... one for each 'column'. (Line them up left to right so it is intuitive). 

    {select}
   {fname}
   {lname}
   {title}
   {phone}
   {_leave_blank_}
{/select}

    [download]
    This is not an 'elegant' solution, but does not seem any worse than giving the user a list of *every possible permutation of the ordering*, (including orderings where zero or more columns are excluded)! The least kludgy solution is to use a GUI control that is intended for this specific purpose. Mozilla Firebird has one. Just something to think about.
[reply]
[d/l]
Re: Re: Permutation seed generator
by blahblah (Friar) on May 06, 2004 at 06:19 UTC

    Geez, the pixels were still warm on my post before you blasted my hilarious code with that 8 liner! Oh woe is me. Days of labor only to see that. ha ha!

    My only question then is how can you set the limit on the length of subsets that get returned. I mean if I only want to see every subset with 2 or more digits? I'm not very familiar with bitshifting and that exponentiation ** thing is throwing me too.

    Oh well. More reading....

    Thanks!

[reply]
      Probably the easiest way to get subsets of a particular size is simply to add a conditional to the print statement: 
      print join " ", @subset, "\n" if @subset == 3;

      [download]
      A little bit more explanation: The number of subsets of a set is 2**$n, with $n the number of elements in the set. So each integer from 0 to 2**n-1 is associated with a unique subset. To get the subset, I associate each bit position with an element of the set. That bit set to 1 means the element is in the subset, 0 means it isn't. The bitshifting and mod operation are used to extract the bit at position $pos to test for membership of that element in the subset.

      -Mark

[reply]
[d/l]
Re: Re: Permutation seed generator
by benizi (Hermit) on May 07, 2004 at 21:20 UTC

    kvale, I like the elegant power set generator, but it doesn't fully solve the OP's question: the power set gives all combinations of a given set, not permutations

    That said, I'd also second scooterm's suggestion that giving all permutations in a list is probably the wrong approach from a UI perspective. Especially so if, as the question seems to imply, you're hoping to scale this solution. With 6 columns, even limiting the choices to orderings of 5 or 6 columns gives you an unwieldy 1,440 options ((6 choose 6 = 1) * 6! + (6 choose 5 = 6) * 5!).

[reply]

In Section Seekers of Perl Wisdom