I've been working on some word puzzles where you are given a list of items (Cars, People, Countries, etc...) and asked to identify a subset of those items that are comprised of a given amount of letters. A simple example could be: 

Word list: TOYOTA HONDA AUDI FORD
Find: 2 words
Given: A(1),D(2),F(1),I(1),O(1),R(1),U(1)
Solution: AUDI FORD

[download]

Small lists can be done by hand with some trial and error but large lists present a huge challenge. I'm trying to figure out how to create a process to solve one of these puzzles given a list of 100 words and asked to find 10 items.

I have a list of 100 dogs and I am given a list of letters that make up 10 of the dog names. I tried to create a process that would identify all of the potential permutations r(10) from n(100) but with 5.35983370e+20 permutations, a linear approach makes this virtually impossible. Still, I gave it shot using Math::Combinatorics to calculate permutations and added a filter to only output records that have the same amount of letters as the given pool (112): 

A(8),B(2),C(5),8(D),7(E),F(1),G(3),H(9),I(8),J(0),K(1),L(9),M(1),N(12)
+,O(13),P(1),Q(0),R(5),S(6),T(4),U(6),V(0),W(1),X(1),Y(0),Z(1)

[download]

This approach just doesn't work due to the number of calculations required. I am hoping the monks have a more elegant solution or at least some ideas for me to explore. My attempt at a solution follows: 

  use Math::Combinatorics;

  open (DOGS, '>>Dogs.txt');
  select DOGS;
  $| = 1;
  my $counter = 0;

  my @n = qw(Affenpinscher AfghanHound AiredaleTerrier Akita AlaskanMa
+lamute AmericanEnglishCoonhound AmericanEskimoDog AmericanFoxhound Ba
+senji BassetHound Beagle BeardedCollie Beauceron BlackandTanCoonhound
+ Bloodhound BluetickCoonhound BorderCollie BorderTerrier Borzoi Bosto
+nTerrier BouvierdesFlandres Boxer BoykinSpaniel Briard Brittany Bruss
+elsGriffon BullTerrier Bulldog Bullmastiff ChesapeakeBayRetriever Chi
+huahua ChineseCrested ChineseShar-Pei Chinook ChowChow ClumberSpaniel
+ CockerSpaniel Collie Curly-CoatedRetriever Dachshund Dalmatian Dandi
+eDinmontTerrier DobermanPinscher DoguedeBordeaux EnglishCockerSpaniel
+ EnglishFoxhound EnglishSetter EnglishSpringerSpaniel GermanPinscher 
+GermanShepherdDog GermanShorthairedPointer GermanWirehairedPointer Gi
+antSchnauzer GlenofImaalTerrier GoldenRetriever GordonSetter GreatDan
+e Greyhound Harrier IbizanHound IcelandicSheepdog IrishSetter IrishTe
+rrier Kuvasz LabradorRetriever LakelandTerrier LhasaApso Lowchen Malt
+ese ManchesterTerrier Mastiff MiniatureBullTerrier MiniaturePinscher 
+MiniatureSchnauzer NeapolitanMastiff Newfoundland NorfolkTerrier Peki
+ngese PembrokeWelshCorgi PharaohHound Plott PortugueseWaterDog Pug Pu
+li PyreneanShepherd RatTerrier ShibaInu ShihTzu SiberianHusky SilkyTe
+rrier SkyeTerrier SmoothFoxTerrier SoftCoatedWheatenTerrier SpinoneIt
+aliano St.Bernard StaffordshireBullTerrier WireFoxTerrier WirehairedP
+ointingGriffon Xoloitzcuintli YorkshireTerrier);
  
  my $combinat = Math::Combinatorics->new(count => 10,
                                          data => [@n],);
  while(my @combo = $combinat->next_combination){
    my $outrec = join('',@combo);

       if (length($outrec) == 112) {
          print DOGS $outrec."\n";
       }
    
       $counter++;
       if ($counter == 100000) {
          print "100000 recs processed"."\n";
          $counter = 0;
       }
  }

  close (DOGS);

[download]
Thank you all for your help and participation!!!

The code from Neighbour did the trick and scaled to puzzles with larger sets of data without consuming memory.

In reply to Another word puzzle with too many permutations by sarchasm

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.