sarchasm has asked for the wisdom of the Perl Monks concerning the following question:
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
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)
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:
Thank you all for your help and participation!!!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);
The code from Neighbour did the trick and scaled to puzzles with larger sets of data without consuming memory.
|
|---|