in reply to counting instances of one array in another array

Good grief, people ... you don't even need a hash. You almost don't need a program.

SELECT PERM, COUNT(*) FROM PERMUTATIONS GROUP BY PERM;

If you need to know the position of a permutation then you can calculate it. The position of ABC = (1,2,3) = 1 + 2*26^2 + 3*26^3, good enuf.

If you then need to generate that huge matrix then ... generate it, as an output, using a nested loop, filling in the minuscule fraction of those entries that are not zero.

You never have to store the entire range of possibilities; you need to store or count what you've actually got.

In the following post, and within ten minutes flat, BrowserUK will now proceed to demonstrate why this reasoning is totally and utterly wrong and why my brain must be disconnected for saying it ...

Replies are listed 'Best First'.
Re^2: counting instances of one array in another array
by LanX (Saint) on Feb 23, 2012 at 18:13 UTC
    > If you need to know the position of a permutation then you can calculate it. The position of ABC = (1,2,3) = 1 + 2*26^2 + 3*26^3, good enuf.

    well this doesn't efficiently encode permutations, but could be sufficient for the OP.

    (until he understands hashes)

    Cheers Rolf

[reply]
Re^2: counting instances of one array in another array
by jsmagnuson (Acolyte) on Feb 24, 2012 at 11:07 UTC

    Thank you for this approach! This is about 10x faster than the next best approach that was suggested here that I tried implementing (which was this code from an AnonymousMonk): 

    my %seen;
$seen{$_}++ for @observed;
@permCounts = map { $seen{$_} || 0 } @perms;

    [download]

    This is good enough to get me going, but I will follow the other advice that was offered and learn about fleximal, PDL::Sparse, and hash-fu. I am very grateful for the generous advice from all of you!

    best,

    jim

    ps -- Slight tweak: abc=(0,1,2), and then 0+(1*26^1)+(2*26^2), etc. (i.e., a=0, z=25, and when string position > 0 you multiply the index of the character in that position by 26 raised to the power of the position).

[reply]
[d/l]

      Re: your ps - see my ngram2number routine above. It does exactly that calculation.

      Update: after re-reading my original message, I note that you also need to translate a list of characters into an alphabet to use the function (just in case it was not understood from the original code). You can do that with: 

      sub charlist2alphabet {
    my %results;
    for my $index ( 0 .. (@_ - 1) ) {
        $results{ $_[ $index ] } = $index;
    }
    \%results;
}

my $alphabet = charlist2alphabet( @charlist );

      [download]
      or 
      my $alphabet = { map { ( $charlist[ $_ ] => $_ ) } ( 0 .. @charlist - 
+1 );

      [download]

      --MidLifeXis

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom