Arrange the numbers such that numbers in a block are unique

Question

Given a string of numbers say "5556778", and a num N(say 2), rearrange the string such that numbers in any continuous block of size N are unique. e.g: for the above string and N=2, one rearrangement can be 5657578.

For N=3: 5765785

find the arrangement in linear time.

Answer 1

Does [String length]/N always equal an integer? Or can the number of elements in the last "Block" != N?

I would make a list of arrays, each array initialized to the size of N.

Iterate through the string, adding each number to the next available block that doesn't already contain that number. Keep going until you are done.

Could be a while loop, or could be a recursive function, I'll leave the implementation details up to you.

EDIT: OK, based on new information, that Blocks are not separate, this appears to be much more like a modified sorting algorithm.

Answer 2

Perhaps this is like bucket sort? Create a list for each digit, and as you encounter each number, add it to the appropriate digit list.

Now, begin building lists of size N from the 10 buckets you've created, pulling from the top of each digit list. If str.length() % N == 0, then this algorithm succeeds when all digits are used. You need to special-case the situations where this is not true, but the rest should be trivial.

Answer 3

O(nk) greedy solution (n = input size, k = radix of your digits), based on Stefan Kendall's answer above, but with the insight that you should probably be greedy and use the integer you have the most of first. I'm not positive it works for all inputs, but I racked my brain trying to think of a counter example where the greed would fail here, and haven't found one yet. Warning: cruddy python ahead - I did this to be quick and dirty, not pretty.

Check whether a digit may be used given the current state:

   def ok(s, n, v):
       l = len(s)
       if l < n:
           n = l
       if n < 1:
           return True
       if str(v) in s[-n:]:
           return False
       return True

Helper which does all the work - loop through the counts, find the one with maximum number of repetitions left which is usable, and select it. Repeat.

   def go(counts, n):
       output = ""
       max = 0
       more = True

       while max >= 0:
         max = -1
         pos = -1
         more = False
         for i in range(10):
             if counts[i] > 0:
                 more = True
             if counts[i] > max and counts[i] > 0 and ok(output, n, i):
                 max = counts[i]
                 pos = i
         if max < 0:
             if more:
                 return "No solution"
             return output
         counts[pos] = counts[pos] - 1
         output = output + str(pos)

Main function:

   def blockify(s, fold):
       counts = [0,0,0,0,0,0,0,0,0,0]
       for letter in s:
         counts[int(letter)] = counts[int(letter)] +1
       return go(counts, fold)

I feel like there's probably a counterexample that this fails on, but I can't think of one.