Re: scrambling all letters in a word until all combinations are found

If you're looking for a canned solution, try Math::Combinatorics (no personal experience).

However, this is a pretty fun problem to code. My brain finds it easiest to think of combinations recursively. For a list of letters, if the desired word length (n) is 1, just return the list. Otherwise iterate through each letter, and find all of the words of length that start with that letter (the current letter appended by all words found in the remaining letters, of length n - 1). Then find the list of words of length n that don't include the current letter. That's it. :) Pseudo code follows (let me know if you'd like a real Perl version; I have one kicking around in my sandbox, as well as a nonrecursive one).

function wordz ($n, @list ) {
  if ( n == 1 ) {
    return @list
  }
  for $current_letter ( @list ) {
    push @words, map { $current_letter . $_ }
      wordz( $n - 1, @letters_sans_current_letter;
    push @words, wordz( $n, @letters_sans_current_letter);
  }
  return @words;
}

-Colin.

WHITEPAGES.COM | INC

Comment on Re: scrambling all letters in a word until all combinations are found

Replies are listed 'Best First'.
Re^2: scrambling all letters in a word until all combinations are found by Anonymous Monk on Jan 23, 2006 at 20:18 UTC
Hi. If you have the code available, I'd love to see the Perl code. So what this is doing is.. @list contains the scrambled letters, ie: @list = (aesfght); Then for each letter, we push it into @words following the next iterated letter. From here, I get kind of lost. Thanks!	[reply]
Re^3: scrambling all letters in a word until all combinations are found by cmeyer (Pilgrim) on Feb 03, 2006 at 18:07 UTC
# takes an integer word length and a list of letters, # returns a list of words of the integer length # { my %cache; sub wordz { my ( $n, @letters ) = @_; my $cache_key = join( '', @letters, $n ); return if $n > @letters; return @letters if $n == 1; return @{ $cache{ $cache_key } } if exists $cache{ $cache_key }; my @wordz; for ( my $i = 0; $i <= $#letters; $i++ ) { push @wordz, map { $letters[ $i ] . $_ } wordz( $n - 1, @letters[ 0 .. $i - 1 ], @letters[ $i + 1 .. $#letters ] ); my @o = wordz( $n, @letters[ $i + 1 .. $#letters ] ); push @wordz, @o; } $cache{ $cache_key } = \@wordz; return @wordz; } } [download] It is also fun to do this problem non-recursively. If you are interested in that, I also have code (though there are different possible approaches). -Colin. WHITEPAGES.COM \| INC	[reply] [d/l]


good chemistry is complicated, and a little bit messy -LW
	PerlMonks