Fixed sequence permutation

Question

I was wondering if anyone could give me us some hints as to what my permutation would require.

I have a string "ABC". And I want to conserve the order of "ABC" but insert a variety of variation of other characters around it. So for example the character "X".

Heres an example:

Given "ABC" and size n = 5, produce List<string> each of size n, with the conserved sequence spread throughout

A B C X X
A X B C X
A X B X C
A X X B C 
X A B C X
X A B X C
X A X B C
X X A B C

So with the insertion of n=2 is pretty trivial. I want to extend this to any n.....

"ABC" and n=8

A B C X X X X X

...

X X A X B X C X

...

X X X X X A B C

So, this code gives the indices of the "X"s for a two-X problem....

int n = 5;
for (int i=0; i<n; i++ ){
    for (int j=i+1; j<n; j++ ) {
        System.out.println(i + "- " +j);
    }
}

So how would one extend this so that given any n, if will produce an n based output, instead of one associated with i and j...? No answers wanted, just a hint of how to extend this. I dont know how many X's there will be, nor the length of the string input - until these are given by a user say.

Thanks greatly, NDG.

Answer 1

One way to do generate all the combinations is by relying on a recursive method that will call itself as long as you don't have a String of the expected size that you could build with a StringBuilder. The recursivity allows to implicitly execute a dynamic amount of nested loops which seems to be your current issue.

public static void main(String[] args) {
    // Permutes to get all possible Strings of size 5
    System.out.println(permute(5));
}

public static List<String> permute(int n) {
    List<String> result = new ArrayList<>();
    // Initialize the SringBuilder with ABC and the target size
    permute(n, result, 0, new StringBuilder(n).append("ABC"));
    return result;
}

public static void permute(int n, List<String> result, int start, StringBuilder builder) {
    if (builder.length() == n) {
        // The String is complete so we add it to the combination list
        result.add(builder.toString());
        return;
    }
    // Iterate from start to the length (included) of StringBuilder
    for (int j = start; j <= builder.length(); j++) {
        // Insert X at the position j
        builder.insert(j, 'X');
        // Continue adding X but starting from next index
        permute(n, result, j + 1, builder);
        // Remove X at the position j
        builder.deleteCharAt(j);
    }
}

Output:

[XXABC, XAXBC, XABXC, XABCX, AXXBC, AXBXC, AXBCX, ABXXC, ABXCX, ABCXX]

Answer 2

here is a python script that will give you the algorithm to get the result. you can adapt it for whatever language you may use.

#!/usr/bin/env python

def comb(n, m, s):
   global a
   r = reversed(range(n))
   for i in r:
      if m > 1:
         comb(i, m-1,s + str(i))
      else:
         b = a[:]
         p = s + str(i)

         for j in range(len(p)):
             b[int(p[j])] = letters[j]
         print(''.join(reversed(b)))


letters = 'ABC'
a = list('X' * 8);
comb(8, 3, '')

#ABCXXXXX
#ABXCXXXX
#ABXXCXXX
#ABXXXCXX
#ABXXXXCX
#ABXXXXXC
#AXBCXXXX
#AXBXCXXX
#AXBXXCXX
#...