count and iterate arrangements of a sequence

Question

I have a string and a number of spaces e.g. the string is "accttgagattcagt" and I have 10 spaces to insert.

How can you iterate over all combinations of that string and spaces? The letters in the string cannot be reordered, and all spaces must be inserted.

And how can you calculate the number of rearrangements (without iterating them)?

And what is the proper word for this? Permutations, combinations or something else?

(I visualise this as strings of 1s and 0s where the 1s are used by the string and the 0s are spaces.

So a short string of 3 letters and 2 spaces would be asking for all all 5 bit numbers with 3 1s and 2 0s e.g. 11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111?

But easy as short sequences are to make on paper, I am struggling to make a for-loop to do it :(. So nice pseudocode to create this sequence, and count how long it would be, please?

Recursion will be easier to understand but can it be faster if recursion is avoided somehow?)

Answer 1

Hmm, a bit pseudo code, but you should get the idea

list doThat(string, spaces){
    returnList
    spacesTemp = spaces;
    for(c = 0; c < string.length; c++){
        subString = string.getSubString(c, string.length);
        tmpString = string.insertStringAtPosition(c, createSpaceString(spacesTemp);
        retSubStringList = doThat(subString, spaces - spacesTemp);
        retCombinedList = addStringInFrontOfAllStringsInList(tmpString, retSubStringList);
        returnList.addList(retCombinedList);
        spacesTemp--;
    }
    return returnList;
}

Answer 2

That's combinations.

So a short string of 3 letters and 2 spaces would be asking for all all 5 bit numbers with 3 1s and 2 0s e.g. 11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111?

You put the three '1's on one of the 5 indices and order does not matter. So its 5 over 3:

5!/((5-3)!3!) = 5*4/(2*1) = 10

The article on wikipedia.org has an image illustrating a random sequence of 3 red and 2 white squares.

This might be useful: Statistics: combinations in Python

Answer 3

n - number of letters m - number of spaces

Counting

Denote number of spaces between first and second letter as a_1, between second and third as a_2 and so on. Your question can now be stated as: In how many different ways a_1, a_2 ..a_n-1 can be chosen that each number is not less than 0 and their sum satisfies a_1 + a_2 .... + a_(n-1) = m? Answer to this question is n + m over n (by over I mean Newton symbol).

Why is it so? Visualize this problem as n + m empty bins in a row. If we fill exactly n of them with sand, distances between filled ones will satisfy our requirements for sum of a_1 ... a_n-1.

Generation

def generate(s, num_spaces):
  ans = generate_aux("_" + s, num_spaces)
  return [x[1:] for x in ans]


def generate_aux(s, num_spaces) : # returns list of arrangements
  if num_spaces == 0:
    return [s]
  if s == "":
    return []
  val = []
  for i in range(0, num_spaces + 1):
    tmp = generate_aux(s[1:], num_spaces - i)
    pref = s[0] + (" " * i)
    val.extend([pref + x for x in tmp])
  return val

print generate("abc", 2)