Algorithm to create all permutations and lengths

Question

I am looking to create an algorithm preferably in Java. I would like to go through following char array and create every possible permutations and lengths out of it.

For example, loop and print the following:

a
aa
aaaa
aaaaa
.... keep going ....
aaaaaaaaaaaaaaaaa ....
ab
aba
abaa .............

Till I hit all possible lengths and permutations from my array.

private void method(){
    char[] data = "abcdefghiABCDEFGHI0123456789".toCharArray();
    // loop and print each time
}

I think it would be silly to come up with 10s of for loops for this. I am guessing some form of recursion would help here but can't get my head around to even start with. Could I get some help with this please? Even if pointing me to a start or a blog or something. Been Googling and looking around and many permutations examples exists but keeps to fixed max length. None seems to have examples on multiple length + permutations. Please advice. Thanks.

Answer 1

Another way to do it is this:

public class HelloWorld{
    public static String[] method(char[] arr, int length) {
      if(length == arr.length - 1) {
        String[] strArr = new String[arr.length];

        for(int i = 0; i < arr.length; i ++) {
            strArr[i] = String.valueOf(arr[i]);
        }

        return strArr;
      }


      String[] before = method(arr, length + 1);
      String[] newArr = new String[arr.length * before.length];
      for(int i = 0; i < arr.length; i ++) {
        for(int j = 0; j < before.length; j ++) {
          if(i == 0)
            System.out.println(before[j]);

          newArr[i * before.length + j] = (arr[i] + before[j]);
        }
      }

      return newArr;
    }

    public static void main(String []args){
        String[] all = method("abcde".toCharArray(), 0);

        for(int i = 0; i < all.length; i ++) {
          System.out.println(all[i]);
        }
    }
}

However be careful you'll probably run out of memory or the program will take a looooong time to compile/run if it does at all. You are trying to print 3.437313508041091e+40 strings, that's 3 followed by 40 zeroes.

Here's the solution also in javascript because it starts running but it needs 4 seconds to get to 4 character permutations, for it to reach 5 character permutations it will need about 28 times that time, for 6 characters it's 4 * 28 * 28 and so on.

const method = (arr, length) => {
  if(length === arr.length - 1)
    return arr;

  const hm = [];
  const before = method(arr, length + 1);
  for(let i = 0; i < arr.length; i ++) {
    for(let j = 0; j < before.length; j ++) {
      if(i === 0)
        console.log(before[j]);

      hm.push(arr[i] + before[j]);
    }
  }

  return hm;
};

method('abcdefghiABCDEFGHI0123456789'.split(''), 0).forEach(a => console.log(a));

Answer 2

private void method(){
    char[] data = "abcdefghiABCDEFGHI0123456789".toCharArray();
    // loop and print each time
}

With your given input there are 3.43731350804×10E40 combinations. (Spelled result in words is eighteen quadrillion fourteen trillion three hundred ninety-eight billion five hundred nine million four hundred eighty-one thousand nine hundred eighty-four. ) If I remember it correctly the maths is some how

1  +  x  +  x^2  +  x^3  +  x^4  +  ...  +  x^n = (1 - x^n+1) / (1 - x)

in your case

28 + 28^2 + 28^3 + .... 28^28

cause you will have

28 combinations for strings with length one

28*28 combinations for strings with length two

28*28*28 combinations for strings with length three

...

28^28 combinations for strings with length 28

It will take a while to print them all.

One way I can think of is to use the Generex library, a Java library for generating String that match a given regular expression.

Generex github. Look at their page for more info.

Generex maven repo. Download the jar or add dependency.

Using generex is straight forward if you are somehow familiar with regex.

Example using only the first 5 chars which will have 3905 possible combinations

public static void main(String[] args) {
    Generex generex = new Generex("[a-e]{1,5}");
    System.out.println(generex.getAllMatchedStrings().size());
    Iterator iterator = generex.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

Meaning of [a-e]{1,5} any combination of the chars a,b,c,d,e wit a min length of 1 and max length of 5

output

a
aa
aaa
aaaa
aaaaa
aaaab
aaaac
aaaad
aaaae
aaab
aaaba
aaabb
aaabc
aaabd
aaabe
aaac
....
eeee
eeeea
eeeeb
eeeec
eeeed
eeeee

Answer 3

You can have a for loop that starts from 1 and ends at array.length and in each iteration call a function that prints all the permutations for that length.

public void printPermutations(char[] array, int length) {
  /*
   * Create all permutations with length = length and print them
   */
}

public void method() {
  char data = "abcdefghiABCDEFGHI0123456789".toCharArray();

  for(int i = 1; i <= data.length; i ++) {
    printPermutations(data, i);
  }
}

Answer 4

I think the following recursion could solve your problem:

  public static void main(String[] args) {
    final String[] data = {"a", "b", "c"};
    sampleWithReplacement(data, "", 1, 5);
  }

  private static void sampleWithReplacement(
      final String[] letters,
      final String prefix,
      final int currentLength,
      final int maxLength
  ) {
    if (currentLength <= maxLength) {
      for (String letter : letters) {
        final String newPrefix = prefix + letter;
        System.out.println(newPrefix);
        sampleWithReplacement(letters, newPrefix, currentLength + 1, maxLength);
      }

    }
  }

where data specifies your possible characters to sample from.

Answer 5

Is this what you're talking about?

public class PrintPermutations
{
    public static String stream = "";

    public static void printPermutations (char[] set, int count, int length)
    {
        if (count < length)
            for (int i = 0; i < set.length; ++i)
            {
                stream += set[i];
                System.out.println (stream);

                printPermutations (set, count + 1, length);
                stream = stream.substring (0, stream.length() - 1);
            }
    }

    public static void main (String[] args)
    {
        char[] set = "abcdefghiABCDEFGHI0123456789".toCharArray();
        printPermutations (set, 0, set.length);
    }
}

Test it using a smaller string first.

Answer 6

On an input string 28 characters long this method is never going to end, but for smaller inputs it will generate all permutations up to length n, where n is the number of characters. It first prints all permutations of length 1, then all of length 2 etc, which is different from your example, but hopefully order doesn't matter.

static void permutations(char[] arr)
{
    int[] idx = new int[arr.length];
    char[] perm = new char[arr.length];

    Arrays.fill(perm, arr[0]);

    for (int i = 1; i < arr.length; i++)
    {
        while (true)
        {
            System.out.println(new String(perm, 0, i));

            int k = i - 1;
            for (; k >= 0; k--)
            {
                idx[k] += 1;
                if (idx[k] < arr.length)
                {
                    perm[k] = arr[idx[k]];
                    break;
                }
                idx[k] = 0;
                perm[k] = arr[idx[k]];
            }
            if (k < 0)
                break;
        }
    }
}

Test:

permutations("abc".toCharArray());

Output:

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc