Brute-Force-like array

Discussion in 'Perl Misc' started by Susanne, Jul 29, 2004.

  1. Susanne

    Susanne Guest

    Hello,

    i want to write a subroutine, that creates something like an
    "brute-force-array" (i don't know a better name for this).

    It should work like this: the subroutine gets a parameter e.g. "3".

    Then the subroutine returns an Array with a,bc....aa,ab,ac....aaa,aab.....

    Does someone have an idea how to solve this?

    Susanne
     
    Susanne, Jul 29, 2004
    #1
    1. Advertising

  2. Susanne

    Paul Lalli Guest

    On Thu, 29 Jul 2004, Susanne wrote:

    > Hello,
    >
    > i want to write a subroutine, that creates something like an
    > "brute-force-array" (i don't know a better name for this).


    Coming up with one would help define your problem.

    > It should work like this: the subroutine gets a parameter e.g. "3".
    >
    > Then the subroutine returns an Array with a,bc....aa,ab,ac....aaa,aab.....
    >
    > Does someone have an idea how to solve this?


    Solve what? You have not at all defined your problem statement. You've
    shown input, you've shown something resembling output, but you haven't
    come close to telling us how one relates to the other.

    What does '3' have to do with what you showed us? Is it the number of
    letters used in the resulting data? Is it the maximum length of the
    string in the resulting data? Is it the maxium length of a subset in the
    resulting data?

    And what exactly *is* the output? A series of strings? A collection of
    arrays of strings?

    You need to be a lot more precise with what you're trying to do before
    you'll get any helpful advise.

    While you're at it, check out the FAQ answer to "How do I permute N
    elements of a list?" to see if that gives you any ideas.
    perldoc -q permute


    Paul Lalli
     
    Paul Lalli, Jul 29, 2004
    #2
    1. Advertising

  3. Susanne

    Susanne Guest

    ok...sorry:

    i have got this:

    my @test = (a,b,c);
    my $length = 4;

    foreach $letter(@test){
    for (my $i =0; $i<=3; $i++){
    $out = $letter.$test[$i];
    push (my @array, $out);
    }
    }
    return @array;


    but this way i only got [a, aa, ab, ac, ad, ae....] but nothing over two
    letters. but i also want the values "aaa, aab, aac, aba...." in my array.
    The length should be given bei the $length-String.

    I hope it's more clear now.


    Susanne
     
    Susanne, Jul 29, 2004
    #3
  4. Susanne

    Paul Lalli Guest

    On Thu, 29 Jul 2004, Susanne wrote:

    > ok...sorry:
    >
    > i have got this:
    >
    > my @test = (a,b,c);
    > my $length = 4;
    >
    > foreach $letter(@test){
    > for (my $i =0; $i<=3; $i++){
    > $out = $letter.$test[$i];
    > push (my @array, $out);
    > }
    > }
    > return @array;
    >


    No you don't. This produces no output, as @array is completely empty when
    you leave the for loops. Post real code.

    >
    > but this way i only got [a, aa, ab, ac, ad, ae....]


    No you didn't. There's no way to produce ad or ae with that code. Post
    real results.

    > but nothing over two
    > letters. but i also want the values "aaa, aab, aac, aba...." in my array.
    > The length should be given bei the $length-String.


    1) I ask again - the length of what? The maximum length of the string in
    the resulting array? Or the maximum size of the array itself?

    2) You're not using $length anywhere after declaring it. How are you
    expecting it to work?

    > I hope it's more clear now.


    Mildly. Did you look at the "permute" documentation I posted earlier? It
    should be possible to do this fairly easily using the List::permutor
    module it refers to...

    Paul Lalli

    P.S. When replying, please include the text you're replying to, above
    your reply. Thanks.
     
    Paul Lalli, Jul 29, 2004
    #4
  5. Susanne

    Paul Lalli Guest

    On Thu, 29 Jul 2004, Paul Lalli wrote:

    > > ok...sorry:
    > >
    > > i have got this:
    > >
    > > my @test = (a,b,c);
    > > my $length = 4;
    > >
    > > foreach $letter(@test){
    > > for (my $i =0; $i<=3; $i++){
    > > $out = $letter.$test[$i];
    > > push (my @array, $out);
    > > }
    > > }
    > > return @array;
    > >
    > > I hope it's more clear now.

    >
    > Mildly. Did you look at the "permute" documentation I posted earlier? It
    > should be possible to do this fairly easily using the List::permutor
    > module it refers to...


    I got bored while waiting for some clients at work... This is my first
    attempt. It's not at all efficient, and I'm sure others here would be
    able to make it much cleaner. But it does produce (what I believe to be)
    your desired output:

    #!/usr/bin/env perl
    use strict;
    use warnings;
    use List::permutor;

    my @data = qw/a b c d/;

    my %results; #where we'll store each string we find

    sub perm {
    return unless @_; #base case for recursion is just to exit

    my $perm = new List::permutor @_;
    while (my @tempresults = $perm->next){
    #join each subset into a string, and record it
    $results{join '', @tempresults}++;
    }

    #remove one element at a time from data, and permute the result
    for my $i (0 .. $#_){
    my @temp = @_;
    splice @temp, $i, 1;
    perm(@temp);
    }
    }

    #start everything off
    perm (@data);

    #Get one copy each of each string found.
    my @results = sort keys %results;
    print "@results\n";
    __END__

    a ab abc abcd abd abdc ac acb acbd acd acdb ad adb adbc adc adcb b ba bac
    bacd bad badc bc bca bcad bcd bcda bd bda bdac bdc bdca c ca cab cabd cad
    cadb cb cba cbad cbd cbda cd cda cdab cdb cdba d da dab dabc dac dacb db
    dba dbac dbc dbca dc dca dcab dcb dcba
     
    Paul Lalli, Jul 29, 2004
    #5
  6. Susanne

    Guest

    "Susanne" <> writes:

    > ok...sorry:
    >
    > i have got this:
    >
    > my @test = (a,b,c);
    > my $length = 4;
    >
    > foreach $letter(@test){
    > for (my $i =0; $i<=3; $i++){
    > $out = $letter.$test[$i];
    > push (my @array, $out);
    > }
    > }
    > return @array;
    >
    >
    > but this way i only got [a, aa, ab, ac, ad, ae....] but nothing over two
    > letters. but i also want the values "aaa, aab, aac, aba...." in my array.
    > The length should be given bei the $length-String.
    >

    sub brute_array {
    my $length = shift;
    my $test = shift;


    my $combo = sub {
    my ($a,$b) = @_;
    my @r = ();
    for (@$a) {
    my $s = $_;
    for (@$b) {
    push (@r, $s . $_);
    };
    };
    return \@r;
    };


    my $s = [""];
    my @r = ();
    for (1 .. $length) {
    $s = &$combo ($s, $test);
    push (@r, @$s);
    };
    return \@r;
    };



    Klaus Schilling
     
    , Jul 29, 2004
    #6
  7. Susanne

    Anno Siegel Guest

    bowsayge <> wrote in comp.lang.perl.misc:
    > Susanne said to us:
    >
    > [...]
    > > but this way i only got [a, aa, ab, ac, ad, ae....] but nothing over two
    > > letters.

    > [...]
    >
    > Is something like this what you want to do?
    >
    > #!/usr/bin/perl
    > use strict;
    > use warnings;
    >
    > my ($length, @test) = (4, 'a'..'c');
    >
    > sub func {
    > my ($bref, $depth) = (@_);
    > if ($depth >= $length) {
    > print "$bref\n";
    > return;
    > }
    > foreach my $var (@test) {
    > func("$bref$var", $depth + 1);
    > }
    > }
    >
    > func '', 0;
    >
    >
    > The length of the string is always 4 chars with this program.
    > Bowsayge doesn't know how to include the shorter strings such
    > as "aa, ab, ... abc". Perhaps someone can modify the program
    > to get those too?


    Very easy. Just call the function with different values in the
    global $length:

    for ( 1 .. 4 ) (
    $length = $_; # loop var would have been aliased
    func '', 0;
    }

    But the length and also the alphabet (@test) should really be
    function parameters, not globals.

    sub func {
    my ($bref, $depth, $length, @alphabet) = (@_);
    if ($depth >= $length) {
    print "$bref\n";
    return;
    }
    foreach my $var (@alphabet ) {
    func("$bref$var", $depth + 1, $length, @alphabet);
    }
    }

    func( '', 0, $_, 'a' .. 'c') for 1 .. 4;

    This still isn't very pretty. The first two parameters are only
    needed to start the recursion off, the user (of func()) shouldn't
    have to deal with them. The standard solution is to make func() an
    internal routine "_func_recurs" (say) and give the user (untested):

    sub func {
    my ( $length, @alphabet) = @_;
    _func_recurs( '', 0, $length, @alphabet);
    }

    There may be better ways to integrate the call.

    Anno
     
    Anno Siegel, Jul 30, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Apps
    Replies:
    3
    Views:
    7,837
    Alvin Bruney [MVP - ASP.NET]
    May 26, 2005
  2. David List

    Re: brute force

    David List, Aug 22, 2003, in forum: C++
    Replies:
    4
    Views:
    608
    Karl Heinz Buchegger
    Aug 22, 2003
  3. Stuart Golodetz

    Re: brute force

    Stuart Golodetz, Aug 22, 2003, in forum: C++
    Replies:
    2
    Views:
    491
    Stuart Golodetz
    Aug 23, 2003
  4. Bas

    Brute force sudoku cracker

    Bas, Sep 16, 2005, in forum: Python
    Replies:
    21
    Views:
    3,221
    Dennis Lee Bieber
    Sep 23, 2005
  5. Replies:
    8
    Views:
    450
Loading...

Share This Page