Generate all permutations of a certain length

Question

Suppose we have the alphabet "abcdefghiklimnop". How can I recursively generate permutations repeating this alphabet in FIVE groups in an efficient way?

I struggled with this a few days later. Any feedback would be helpful.

Essentially this is the same as: Generating all permutations of a given string

However, I just want the permutations to be FIVE-wide throughout the line. And I could not understand it.

SO for all substrings of length 5 "abcdefghiklimnop", find permutations of the substring. For example, if the substring was abcdef, I would like all permutations of this, or if the substring was defli, I would like all permutations of this substring. The code below gives me all permutations of a string, but I would like to use to find all permutations of all substrings of size 5 rows.

public static void permutation(String str) { permutation("", str); } private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0) System.out.println(prefix); else { for (int i = 0; i < n; i++) permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); } } 

Answer 1

To select five characters from a string recursively, perform a simple algorithm:

• Your method should get the part filled so far and the first position in a five-character permutation that needs a character
• If the first position that needs a character is above five, you do; type the combination you have and return
• Otherwise, put each character at the current position in the permutation and make a recursive call

In Java, this is much shorter:

 private static void permutation(char[] perm, int pos, String str) { if (pos == perm.length) { System.out.println(new String(perm)); } else { for (int i = 0 ; i < str.length() ; i++) { perm[pos] = str.charAt(i); permutation(perm, pos+1, str); } } } 

The caller controls the desired permutation length by changing the number of elements in perm :

 char[] perm = new char[5]; permutation(perm, 0, "abcdefghiklimnop"); 

Demo version

Answer 2

All five-character permutations will be contained in the set of the first five characters of each permutation. For example, if you want all two character permutations in the four-character string "abcd" you can get them from all permutations: 'abcd', 'abdc', 'acbd', 'acdb' ... 'dcba'

Therefore, instead of printing them in your method, you can save them in a list after checking to make sure that this permutation is already saved. The list can be passed to a function or a static field depending on your specification.

Answer 3

This can be easily done using bit manipulation.

 private void getPermutation(String str, int length) { if(str==null) return; Set<String> StrList = new HashSet<String>(); StringBuilder strB= new StringBuilder(); for(int i = 0;i < (1 << str.length()); ++i) { strB.setLength(0); //clear the StringBuilder if(getNumberOfOnes(i)==length){ for(int j = 0;j < str.length() ;++j){ if((i & (1 << j))>0){ // to check whether jth bit is set (is 1 or not) strB.append(str.charAt(j)); } } StrList.add(strB.toString()); } } System.out.println(Arrays.toString(StrList.toArray())); } private int getNumberOfOnes (int n) // to count how many numbers of 1 in binary representation of n { int count=0; while( n>0 ) { n = n&(n-1); count++; } return count; }