How to Get All the Possible 3 Letter Permutations

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);

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.

How can I generate a list of all possible permutations of several letters?

to generate all permutations of a given list of letters, use the itertools module.

import itertools 
for word in itertools.permutations( list_of_letters ):
   print ''.join(word)

All possible permutations of a few letters with varying lengths of combination allowed

You can use combn to create the combinations and the paste the elements within each combination as follows:

l <- c("A", "R", "N", "T", "F", "G", "B")
unlist(lapply(2:5, function(n) combn(l, n, paste, collapse="")))

output:

  [1] "AR"    "AN"    "AT"    "AF"    "AG"    "AB"    "RN"    "RT"    "RF"    "RG"    "RB"    "NT"    "NF"    "NG"    "NB"    "TF"    "TG"    "TB"    "FG"    "FB"   
 [21] "GB"    "ARN"   "ART"   "ARF"   "ARG"   "ARB"   "ANT"   "ANF"   "ANG"   "ANB"   "ATF"   "ATG"   "ATB"   "AFG"   "AFB"   "AGB"   "RNT"   "RNF"   "RNG"   "RNB"  
 [41] "RTF"   "RTG"   "RTB"   "RFG"   "RFB"   "RGB"   "NTF"   "NTG"   "NTB"   "NFG"   "NFB"   "NGB"   "TFG"   "TFB"   "TGB"   "FGB"   "ARNT"  "ARNF"  "ARNG"  "ARNB" 
 [61] "ARTF"  "ARTG"  "ARTB"  "ARFG"  "ARFB"  "ARGB"  "ANTF"  "ANTG"  "ANTB"  "ANFG"  "ANFB"  "ANGB"  "ATFG"  "ATFB"  "ATGB"  "AFGB"  "RNTF"  "RNTG"  "RNTB"  "RNFG" 
 [81] "RNFB"  "RNGB"  "RTFG"  "RTFB"  "RTGB"  "RFGB"  "NTFG"  "NTFB"  "NTGB"  "NFGB"  "TFGB"  "ARNTF" "ARNTG" "ARNTB" "ARNFG" "ARNFB" "ARNGB" "ARTFG" "ARTFB" "ARTGB"
[101] "ARFGB" "ANTFG" "ANTFB" "ANTGB" "ANFGB" "ATFGB" "RNTFG" "RNTFB" "RNTGB" "RNFGB" "RTFGB" "NTFGB"

Generating all n-letter permutations

For a specific and small, n, manual loops like you have is the easiest way. However, your code can be highly simplified:

for(char a='a'; a<='z'; ++a) {
    for(char b='a'; b<='z'; ++b) {
        if (b==a) continue;
        for(char c='a'; c<='z'; ++c) {
            if (c==a) continue;
            if (c==b) continue;
            std::cout << a << b << c << '\n';
        }
    }
}

For a variable N, obviously we need a different strategy. And, it turns out, it needs an incredibly different strategy. This is based on DaMachk's answer, of using recursion to generate subsequent letters

template<class func_type> 
void generate(std::string& word, int length, const func_type& func) {
    for(char i='a'; i<='z'; ++i) {
        bool used = false;
        for(char c : word) {
            if (c==i) {
                used = true;
                break;
            }
        }
        if (used) continue;
        word.push_back(i);
        if (length==1) func(word);
        else generate(word, length-1, func);
        word.pop_back();
    }
}
template<class func_type> 
void generate(int length, const func_type& func) {
    std::string word;
    generate(word, length, func);
}

You can see it here

I also made an unrolled version, which turned out to be incredibly complicated, but is significantly faster. I have two helper functions: I have a function to "find the next letter" (called next_unused) which increases the letter at an index to the next unused letter, or returns false if it cannot. The third function, reset_range "resets" a range of letters from a given index to the end of the string to the first unused letter it can. First we use reset_range to find the first string. To find subsequent strings, we call next_unused on the last letter, and if that fails, the second to last letter, and if that fails the third to last letter, etc. When we find a letter we can properly increase, we then "reset" all the letters to the right of that to the smallest unused values. If we get all the way to the first letter and it cannot be increased, then we've reached the end, and we stop. The code is frightening, but it's the best I could figure out.

bool next_unused(char& dest, char begin, bool* used) {
    used[dest] = false;
    dest = 0;
    if (begin > 'Z') return false;
    while(used[begin]) {
        if (++begin > 'Z')
            return false;
    }
    dest = begin;
    used[begin] = true;
    return true;
}
void reset_range(std::string& word, int begin, bool* used) {
    int count = word.size()-begin;
    for(int i=0; i<count; ++i)
        assert(next_unused(word[i+begin], 'A'+i, used));
}
template<class func_type>
void doit(int n, func_type func) {
    bool used['Z'+1] = {};
    std::string word(n, '\0');
    reset_range(word, 0, used);
    for(;;) {
        func(word);
        //find next word
        int index = word.size()-1;
        while(next_unused(word[index], word[index]+1, used) == false) {
            if (--index < 0)
                return; //no more permutations
        }
        reset_range(word, index+1, used);
   }
}

Here it is at work.

And here it is running in a quarter of the time as the simple one

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))

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.

Generate a list of all possible patterns of letters

One of the comments, from @JacobRR, was very close to what we need. Each "pattern" actually corresponds to partitioning of set {1, 2, ..., N} into K subsets. Each subset (even empty!) corresponds to the positions where letter l_k should be placed (l_1 = A, l_2 = B etc.). There's a demo here.
https://thewebdev.info/2021/10/28/how-to-generate-set-partitions-in-python

For example, in case K=3, N=3, the partitions would be

{1,2,3}, ∅, ∅
{1}, {2, 3}, ∅
{2}, {1, 3}, ∅
{3}, {1, 2}, ∅
{1}, {2}, {3}

and for K=2, N=3, it's

{1,2,3}, ∅
{1}, {2, 3}
{2}, {1, 3}
{3}, {1, 2}

corresponding exactly to the given examples.

This question is also relevant.

https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions

I also wrote my own naive implementation.

import copy

N = 3
K = 2

iter = min(N, K)

def partitions(S, K):

    if K == 1:
        return [[S]]
    if len(S) == 0:
        return [[]]
    
    result = []
    S_new = copy.copy(S)
    first = S_new.pop(0)
    
    if (K-1 <= len(S_new)):
        p1 = partitions(S_new, K-1)
        for p in p1:
            p.append([first])
            result.append(p)
    if (K <= len(S_new)):
        p2 = partitions(S_new, K)

        for p in p2:
            for idx in range(len(p)):
                p_new = copy.deepcopy(p)
                p_new[idx].append(first)
                result.append(p_new)
                
        
    return result

for idx in range(1, iter+1):
    print(partitions([i for i in range(0, N)], idx))    

How can I create a list with all the possible combinations of common letters between two strings?

You are using your listtostring function wrong, you should use that on every permutation created, not on the whole list of permutations. And you can use capitalize() to capitalize the first letters.

Here is the modified code, I removed your for loop as it wasn't doing anything:

import itertools as itr

def listtostring(s):
    string = ""
    return (string.join(s))

str1=input("Enter 1st string:")
str2=input("Enter 2nd string:")
common_letters=set(set(str1) & set(str2))
print("list of common letters : ",common_letters)

mylist=list(itr.permutations(common_letters))
finalList = [listtostring(x).capitalize() for x in mylist]

print("Words generated from common letters are : ", finalList)

You can change the last line to the following if you want it to all be one string:

print("Words generated from common letters are : ", " ".join(finalList))

---

Related Topics