Finding all possible permutations of the characters in a set of strings using recursion

Question

I have this set of (Greek) strings:

ἸἼΙἹἽ, ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ, σς, οὸόὀὄὅὂ, ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ

I'd like to find all possible permutations of the characters in these 5 strings. For example, Ἰῇσοὺ, Ἰῇσοὖ, Ἰῇσου, etc. I know it should involve recursion since the number of strings is not fixed but I'm a beginner and I'm completely dumbfounded by recursion.

I did the following in Python and it does give me all combinations of the characters in each string. But I need the 'ἸἼΙἹἽ' to always come first, 'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ' second,'σς' third, etc.

# -*- coding: utf-8 -*-

def Gen( wd, pos, chars ):
    if pos < len( chars ):
        for c in chars:
            for l in c:
                Gen( wd + l, pos + 1, chars )
    else:
        print wd

chars = [ u'ἸἼΙἹἽ', u'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ', u'σς', u'οὸόὀὄὅὂ', u'ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ' ]

Gen( "", 0, chars )

Thanks for the help everybody. My mind is completely blown. Recursion! Here's what I ended up doing in Python:

# -*- coding: utf-8 -*-

s = [ u'ἸἼΙἹἽ', u'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ', u'σς', u'οὸόὀὄὅὂ', u'ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ' ]

results = []

def recur( wd, strings ):
    index = 0
    if index < len( strings ):
        for c in strings[ index ]:
            recur( wd + c, strings[ index + 1: ] )
    else:
        results.append( wd )

def main():
    recur( '', s )
    for r in results:
        print r.encode( 'utf-8' )

main()

Kirkcudbright

Use a pen and paper to figure out the algorithm. – Apeldoorn

Ἰῇσοὺ, Ἰῇσοὖ, Ἰῇσου, ... for each u, then each o for each u. then each sigma for each o and u... and so forth. but I don't know how to code that using recursion. – Kirkcudbright

You never have to use recursion. You can work with for/while loops by starting with an array of all unique characters. – Apeldoorn

True, but the number of strings is not fixed. In this case I have 5 strings but in general the user will determine the number of strings.... and the content of each string. – Kirkcudbright

Answer 1

Just write down the five nested loops. In pseudocode,

for a in "ἸἼΙἹἽ"
  for b in "ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ"
    for c in "σς"
      for d in "οὸόὀὄὅὂ"
        for e in "ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ"
           emit [a,b,c,d,e]

To encode these nested loops with recursion, so it's good for any number of input strings, again in pseudocode,

g(list-of-strings) =
   | case list-of-strings
   | of  empty --> end-of-processing
   | of  (first-string AND rest-of-strings) --> 
            for each ch in first-string 
               DO g(rest-of-strings)

Now you only need to figure out where to hold each current first-string's character ch and how to combine them all while at the end-of-processing (basically, your two options are a global accumulator, or an argument to a function invocation).

The latter approach can be coded as

g( picks, list-of-strings) =   # initially, picks = []
   | case list-of-strings
   | of  empty --> end-of-processing( picks )
   | of  (first-string AND rest-of-strings) --> 
            for each ch in first-string 
               DO g( [...picks, ch], rest-of-strings )

Norvin

Answer 2

You create a char array which will contain the string you want to work with char str[] = "ABC";

then you get the length of the string int n = strlen(str); and lastly you permutate.

You make a new function which will contain the input string, starting index of the string and ending index of the string. Check if the starting index (int s) equals the ending index (int e) if it does, that means you're done, if not you go into a loop where you go from start (s) to end (e), swap the values, recurse, swap again to backtrack.

An example in C++:

#include <stdio.h>
#include <string.h>

void swap(char *i, char *j)
{
    char temp;
    temp = *i;
    *i = *j;
    *j = temp;
}

void permutate(char *str, int start, int end)
{
    int i;
    if (start == end)
        printf("%s\n", str);
    else
    {
        for (i = start; i <= end; i++)
        {
            swap((str + start), (str + i));
            permutate(str, start + 1, end);
            swap((str + start), (str + i)); //backtrack
        }
    }
}

int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permutate(str, 0, n - 1);
    return 0;
}

I'm not that familliar with Python, but I've found something that might help in your case:

def comb(first_str, second_str):
if not first_str:
    yield second_str
    return
if not second_str:
    yield first_str
    return

for result in comb(first_str[1:], second_str):
    yield first_str[0] + result
for result in comb(first_str, second_str[1:]):
    yield second_str[0] + result

>>> for result in comb("ἸἼΙἹἽ", "ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ"):
print(result)

Boong