How to Generate All Possible Three Letter Strings

How to generate all possible combinations from the letters of strings in a list

I can propose you a trivial algorithm to do the same, it is using recursion:

def associations(entry):
while len(entry) > 2:
to_treat_later = entry.pop()
print(f"We will treat {to_treat_later} later")
entry = associations(entry)
entry.append(to_treat_later)
else:
print(f"we can start with {entry}")
associated_entry = []
for elt_1 in entry[0]:
for elt_2 in entry[1]:
associated_entry.append(f"{elt_1}{elt_2}")
return [associated_entry]

def convert_entry(entry):
converted_entry = []
for elt in entry:
list_elt = []
for letter in elt:
list_elt.append(letter)
converted_entry.append(list_elt)
return converted_entry

the_entry = ["jkl", "ghi", "def", "cfe"]
associations(convert_entry(the_entry))

What is the best way to generate all possible three letter strings?

keywords = itertools.product(alphabets, repeat = 3)

See the documentation for itertools.product. If you need a list of strings, just use

keywords = [''.join(i) for i in itertools.product(alphabets, repeat = 3)]

alphabets also doesn't need to be a list, it can just be a string, for example:

from itertools import product
from string import ascii_lowercase
keywords = [''.join(i) for i in product(ascii_lowercase, repeat = 3)]

will work if you just want the lowercase ascii letters.

Generating all possible combinations of characters in a string

This looks like a job for itertools.product.

import itertools

def foo(l):
yield from itertools.product(*([l] * 3))

for x in foo('abc'):
print(''.join(x))

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

yield from is available to you from python3.3 and beyond. For older version, yield within a loop:

def foo(l):
for i in itertools.product(*([l] * 3)) :
yield i

How to get all the possible 3 letter permutations?

For a variable amount of letter combinations, you can do the following:

var alphabet = "abcdefghijklmnopqrstuvwxyz";
var q = alphabet.Select(x => x.ToString());
int size = 4;
for (int i = 0; i < size - 1; i++)
q = q.SelectMany(x => alphabet, (x, y) => x + y);

foreach (var item in q)
Console.WriteLine(item);

Algorithm for generating all string combinations

Here's how I would do it in Javascript (I assume that every string contains no duplicate characters):

function getPermutations(arr)
{
return getPermutationsHelper(arr, 0, "");
}

function getPermutationsHelper(arr, idx, prefix)
{
var foundInCurrent = [];
for(var i = 0; i < arr[idx].length; i++)
{
var str = prefix + arr[idx].charAt(i);

if(idx < arr.length - 1)
{
foundInCurrent = foundInCurrent.concat(getPermutationsHelper(arr, idx + 1, str));
}
else
{
foundInCurrent.push(str);
}
}
return foundInCurrent;
}

Basically, I'm using a recursive approach. My base case is when I have no more words left in my array, in which case I simply add prefix + c to my array for every c (character) in my last word.

Otherwise, I try each letter in the current word, and pass the prefix I've constructed on to the next word recursively.

For your example array, I got:

adg adh adi adj aeg aeh aei aej afg afh afi afj bdg bdh bdi 
bdj beg beh bei bej bfg bfh bfi bfj cdg cdh cdi cdj ceg ceh
cei cej cfg cfh cfi cfj

Python generate all 3 letter combinations

Use combinations in the standard library package itertools

import string
from itertools import combinations

letters = list(string.ascii_lowercase)
letters.extend(string.digits)

for comb in combinations(letters, 3):
print(''.join(comb))

How do you generate all 5 letter strings from 3 characters?

Your nested for loops does imply that code can be refactored
either using recursion or as in my example below by creating
a higher level loop.

This approach allows us to generate strings of any desired length.

let characters = "abc";
let desiredLength = 5;

let theSet = [""];
for ( let length = 0; length < desiredLength; length++){
let extendedSet = [];
theSet.forEach( (item) =>
extendedSet.push( ...extendWith( item, characters) )
)
theSet = extendedSet;
}

console.log('result ', theSet);

// given a strings and a set of characters
// generate an array of string extended with each
// of the characters.
// "a" with "xy" generates
// [ "ax", "ay" ]
function extendWith( extendThis, characters){
let result = [];
[...characters].forEach( (c) => result.push(extendThis+c) );
return result;
}

We can make that extendWith function more succinct like this

function extendWith( extendThis, characters){   
return [...characters].map( c => extendThis + c );
}

and as it's now just a one line expression we can dispense with the utility function and simplify a bit more

for ( let length = 0; length < desiredLength; length++){

theSet = theSet.flatMap( (item) =>
[...characters].map( c => item + c )
);

}

Python generate all possible strings of length n

Here's a piece of code that uses [Python 3.Docs]: itertools.product(*iterables, repeat=1).

Note that the number of generated strings is 62 ** length, so for testing purposes use small values for length:

import string
import itertools

def generate_strings(length=3):
chars = string.ascii_letters + string.digits # "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
for item in itertools.product(chars, repeat=length):
yield "".join(item)

Algorithm to generate all possible letter combinations of given string down to 2 letters

For the purpose of writing an anagram solver the kind of which you linked, the algorithm that you are requesting is not necessary. It is also VERY expensive.

Let's look at a 6-letter word like MONKEY, for example. All 6 letters of the word are different, so you would create:

  • 6*5*4*3*2*1 different 6-letter words
  • 6*5*4*3*2 different 5-letter words
  • 6*5*4*3 different 4-letter words
  • 6*5*4 different 3-letter words
  • 6*5 different 2-letter words
  • For a total of 1950 words

Now, presumably you're not trying to spit out all 1950 words (e.g. 'OEYKMN') as anagrams (which they are, but most of them are also gibberish). I'm guessing you have a dictionary of legal English words, and you just want to check if any of those words are anagrams of the query word, with the option of not using all letters.

If that is the case, then the problem is simple.

To determine if 2 words are anagrams of each other, all you need to do is count how many times each letters are used, and compare these numbers!

Let's restrict ourself to only 26 letters A-Z, case insensitive. What you need to do is write a function countLetters that takes a word and returns an array of 26 numbers. The first number in the array corresponds to the count of the letter A in the word, second number corresponds to count of B, etc.

Then, two words W1 and W2 are exact anagram if countLetters(W1)[i] == countLetters(W2)[i] for every i! That is, each word uses each letter the exact same number of times!

For what I'd call sub-anagrams (MONEY is a sub-anagram of MONKEY), W1 is a sub-anagram of W2 if countLetters(W1)[i] <= countLetters(W2)[i] for every i! That is, the sub-anagram may use less of certain letters, but not more!

(note: MONKEY is also a sub-anagram of MONKEY).


This should give you a fast enough algorithm, where given a query string, all you need to do is read through the dictionary once, comparing the letter count array of each word against the letter count array of the query word. You can do some minor optimizations, but this should be good enough.

Alternatively, if you want utmost performance, you can preprocess the dictionary (which is known in advance) and create a directed acyclic graph of sub-anagram relationship.

Here's a portion of such a graph for illustration:

 D=1,G=1,O=1  ----------> D=1,O=1
{dog,god} \ {do,od}
\
\-------> G=1,O=1
{go}

Basically each node is a bucket for all words that have the same letter count array (i.e. they're exact anagrams). Then there's a node from N1 to N2 if N2's array is <= (as defined above) N1's array (you can perform transitive reduction to store the least amount of edges).

Then to list all sub-anagrams of a word, all you have to do is find the node corresponding to its letter count array, and recursively explore all nodes reachable from that node. All their buckets would contain the sub-anagrams.



Related Topics



Leave a reply



Submit