-2

I am looking for the best way of generating all strings permutations in a range.

Here is an example. 

Start : aaaa   
End : cccc

Or for example 

Start : aabb   
End : ccaa

Strings that should be generated for the first case 

aaaa,aaab,aaac,aaba,aabb,aabc,aaca,aacb ... cccc

So I hope you got an idea. All possible permutations.

Please suggest how to solve this problem efficiently. I can write nested loops, but I hope there are some default implementations that are much more efficient.

EDIT

The same as counting in binary system

100
101
110
111

EXAMPLE Start : aaa
End : ccc

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
  • 3
    Duplicate: http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string – mlewandowski Mar 08 '16 at 12:49
  • Have you tried something? – Prashant Mar 08 '16 at 12:51
  • You don't mean permutations , do you? It is completely unclear, what you actually want to do. – ctst Mar 08 '16 at 13:03
  • 1
    Just think of it as counting, where each digit is a letter. –  Mar 08 '16 at 13:17
  • The correct name for this is k-permutations with repetition. –  Mar 08 '16 at 13:17
  • 1
    Are all of the strings the same length? If so, then all you have to do is a base conversion from decimal to base *a*, where *a* is the number of characters in your alphabet and, as @Martin says, start counting. – beaker Mar 08 '16 at 15:35

2 Answers2

0

Your solution is going to need to be inefficient to run whatever you do.

I'd write a 'next' function that increments the last (rightmost) character of the string. If it matches the 'end character' already, I'd set it to the 'start character' and then recursively call the method with the remaining characters (characters 0 through n-1). You will then touch all of the possible values.

(This algorithm doesn't work if you aaa..bbb should include azz because that would be alphabetically sorted between aaa and bbb.)

Jane Nicholson
  • 375
  • 2
  • 12
  • Yes , I don't need to include zz if the range is aaa-ccc, Can you provide example please –  Mar 08 '16 at 13:27
0

Here is an implementation based on the answer of Jane Nicholson: https://jsfiddle.net/3rzse24d/2/

var start = prompt("Start: (ex: aabb)");
var end = prompt("End: (ex: ccaa)");
if (start.length != end.length) {
    alert("They must have the same length!");
    return;
}
if (start > end) {
    var tmp = start;
    start = end;
    end = tmp;
}
var alphabet = prompt("Alphabet: (ex: abc)");
var out = "";

var i, digit, stop;
while (start < end) {
    out += start + "\n";
    stop = false;
    for (i = start.length - 1 ; !stop && i >= 0 ; i-- ) {
        digit = alphabet.indexOf( start.charAt(i) );
        if (digit < 0) {
            alert("Letter `" + start.charAt(i) + "` is not part of the provided alphabet!");
            return;
        }
        digit++;
        stop = digit < alphabet.length;
        start = start.substr(0, i)
            + alphabet.charAt( digit % alphabet.length )
            + start.substr( i + 1 );
    }
    if (!stop) break;
}

document.getElementById("out").textContent = out + end;
Tolokoban
  • 2,297
  • 14
  • 17