1

I have an array:

1 1A 2 2A 3 3A 4 4A 5 5A

I need to Rearrange it by random, with the condition: 1A must behind 1, 2A behind 2...(does not necessarily like 1 1A)

the expect result after rearrange as below:

1 4 2 4A 3 2A 5 1A 5A 3A

Help me for best algorithm ( best in speed )

Improve this question
6
  • 1
    "Best" in which sense? Time? Memory? Distribution? Commented May 29, 2015 at 10:59
  • thanks, i mean best in "time" Commented May 29, 2015 at 11:02
  • 2
    Put the dependent elements into different queues, than randomly pick an element from a random queue until all the queues are empty. Commented May 29, 2015 at 11:02
  • So what is this, a random topological sort? Commented May 29, 2015 at 11:02
  • i not know what is "a random topological sort" :) Commented May 29, 2015 at 11:04

2 Answers 2

Reset to default
5

You could try like this:

  • groups the elements into different queues, such that all the elements that have some 'order' are in the same queue, e.g. [[1, 1A], [2, 2A, 2B], [3, 3A], ...]
  • randomly select one of those queues, remove the first element and add it to your result
  • repeat until all the queues are empty

In case the partial ordering is more complex, e.g. if some element a has to be before b and c, but there is no partial ordering between b and c you could probably do the same with a tree or similar.

Also, as pointed out by @vib, in order to ensure uniform distribution of elements in the result, you should pick the different queues with probability proportional to the number of elements remaining in that queue.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Note that grouping requires mapping/sorting the collection (O(n) space/O(nlogn) time) - it is essentially element distinctness problem.
@amit I thought the grouping would be O(n) time, provided that the sequence is already sorted (as seems to be the case in the question) and you just have to identify the group each element belongs to.
@tobias_k this is correct if sequence is indeed already sorted.
If you want to have something really uniform given the constraints you should not pick the queues uniformly at random but with a probability proportional to their size. Otherwise if you take for instance the case 1 2A 2B 2C .. you would see a one in first position half of the time which is not what you would expect from a random permutation.
@vib That's a good point. Should not be too hard to implement, though. You could just roll a random number from all the numbers and then pick the first element from the queue that number belongs to.
|
2
  • Shuffle the array (Fisher yates shuffle)
  • For each x,xA pair - if x is after xA, switch them. This can be done by creating a map:Element->Index in O(n) for all elements in the array.

Total complexity: O(n) (time) average case
Output is guaranteed to be randomly uniformly shuffle, from correctness of fisher-yates.

Pseudo-code:

array = shuffle(array)
map = new map
for each element e in array with index i:
    map.add(e,i)
for each element e in the array:
   if e is "x" (not "xA"):
       i = map.get(e)
       j = map.get(xA)
       if j<i:
         swap(arr,i,j)
  • If there are more than only 2 (x,xA,xB,...) - you can list them all and sort in the main loop, in a similar way.
Improve this answer

2 Comments

thanks you, but i think the tobias 's solution is good and easy for me
is the "Random pick" algorithm faster than the "shuffle" algorithm?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.