Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

•Re: Puzzle: need a more general algorithm

by merlyn (Sage)
on Jul 08, 2002 at 20:35 UTC ( #180316=note: print w/ replies, xml ) Need Help??


in reply to Puzzle: need a more general algorithm

One other thing to notice is that a particular distribution can be identified by a binary string of length equal to one less than the number of categories, and a number of 1-bits equal to one less than the number of columns. Each 0-bit denotes that the next category is in the same column as the prior category, while a 1-bit denotes that the next category begins the next column over. Since the first category is forced into the first column, and the last category is forced into the last column, we get two freebies there.

So the total number of distributions of N categories into M columns is equal to the number of combinations of N-1 things taken M-1 at a time.

Dunno if this helps, but it should keep you from brute forcing more than you need. {grin}

In fact, for your particular dataset (6 categories, 4 columns), you shouldn't need to brute force more than (5 items taken 3 at a time which is) 10 tries.

Wow, that's less than I thought! But it desk checks properly. All you need is a good generating algorithm, and you can brute force this!

-- Randal L. Schwartz, Perl hacker


Comment on •Re: Puzzle: need a more general algorithm
Re: •Re: Puzzle: need a more general algorithm
by Anonymous Monk on Jul 08, 2002 at 21:21 UTC
    Counter example:
    1 2 3 4 1 2 3 4 1 2 3 4 5 6 5 6 5 6 1 3 4 5 1 3 4 5 1 3 4 5 2 6 2 6 2 6 1 2 3 6 1 2 3 6 1 2 3 6 4 5 4 5 4 5 1 2 3 6 1 2 3 6 1 2 3 6 4 5 4 5 4 5 ...

    That's twelve tries and there are more still.

      That's twelve tries and there are more still.

      No, there are only 10. Your attempt at a counter example violates the requirement that "The categories must remain in order".

        My apologies. I misread that requirement entirely.
Re: •Re: Puzzle: need a more general algorithm
by Ovid (Cardinal) on Jul 09, 2002 at 05:03 UTC

    merlyn wrote: All you need is a good generating algorithm and you can brute force this!

    I thought this idea was so intensely cool that I just had to try it out. However, coming up with a "good generating alorithm" escapes me. First, I took the list of possible permutations that dws created and translated it:

    [1][2][3][4,5,6] 1 1 1 0 0 [1][2][3,4][5,6] 1 1 0 1 0 [1][2][3,4,5][6] 1 1 0 0 1 [1][2,3][4][5,6] 1 0 1 1 0 [1][2,3][4,5][6] 1 0 1 0 1 [1][2,3,4][5][6] 1 0 0 1 1 [1,2][3][4][5,6] 0 1 1 1 0 [1,2][3][4,5][6] 0 1 1 0 1 [1,2][3,4][5][6] 0 1 0 1 1 [1,2,3][4][5][6] 0 0 1 1 1

    Then, once I was sure I understood it, I went ahead and hardcoded that so I could manipulate it and look for patterns.

    #!/usr/bin/perl -w use strict; use Data::Dumper; my @categories = qw/ 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111 /; @categories = sort @categories; my @cat2 = sort { $a <=> $b } map { ord pack 'b*', $_ } @categories; print Dumper \@categories, \@cat2;

    Which prints the following:

    $VAR1 = [ '00111', '01011', '01101', '01110', '10011', '10101', '10110', '11001', '11010', '11100' ]; $VAR2 = [ 7, 11, 13, 14, 19, 21, 22, 25, 26, 28 ];

    Needless to say, the list seems arbitrary (even though we know it's not) and try as I might, I can't come up with a method of creating that, much less writing a generalized routine. I thought about trying to discover a pattern in the sequences, but no dice. Later, I tried creating a "picture" of the bits and swapping pairs, but I couldn't come up with a sequence for that, either. I'll start looking into permutators, but I feel like I'm missing something awfully basic here. There are only 10 possible combinations, so I didn't think generating them would be that hard :(

    Cheers,
    Ovid

    Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

        '00111', '01011', '01101', '01110', '10011', '10101', '10110', '11001', '11010', '11100'

      So it looks like you're shifting the highest bit up by one, then the next highest bit, then the next, until you've run out of empty bits. How about something like (untested):

      use Bit::Vector; my $joins = 2; my $splits = 3; my $length = $joins+$splits; my $start = '0'x$joins . '1'x$splits; my $vector = Bit::Vector->new_Bin($length, $start); my @combinations = (); for my $pos ($joins-1..$length-1) { # 0-based, right? for my $bit ($splits-1..0) { $vector->bit_flip($pos+$bit); $vector->bit_flip($pos+$bit-1); push @combinations, $vector->to_Bin(); } }

      --
      The hell with paco, vote for Erudil!
      :wq

        Tempting, but the this is the "swapping bits" that I was referring to. The solution skips these three combinations:

        01101 01110 10110

        If you look at them closely, you'll see why you can't generate them. That's what got me stuck on this track. If that can be solved, this is a good way to go.

        Oh, and since you mentioned this was untested, I won't comment about for my $bit ($splits-1..0) { :)

        Cheers,
        Ovid

        Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

      As we discussed in that meeting, here's the code snippet I was thinking about to generate the binary strings:
      print map "$_\n", strings_for(6, 4); sub strings_for { my ($cats, $cols) = @_; $cats--; $cols--; my @ret; for (0..(1 << $cats) - 1) { my $bitstring = substr(unpack("B*", pack "N", $_), -$cats); next unless $bitstring =~ tr/1// == $cols; push @ret, $bitstring; } @ret; }

      -- Randal L. Schwartz, Perl hacker

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180316]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2014-09-18 04:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (108 votes), past polls