Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

In-place array reordering?

Tags:

Let's say I have an array a of length n and a second array indices, also of length n. indices contains some arbitrary permutation of the sequence [0, n). I want to to rearrange a such that it's in the order specified by indices. For example, using D syntax:

auto a = [8, 6, 7, 5, 3, 0, 9]; auto indices = [3, 6, 2, 4, 0, 1, 5]; reindexInPlace(a, indices); assert(a == [5, 9, 7, 3, 8, 6, 0]); 

Can this be done in both O(1) space and O(n) time, preferably without mutating indices?

like image 959
dsimcha Avatar asked Sep 09 '11 18:09

dsimcha


People also ask

How do you rearrange an array in C++?

Approach used in the below program is as followsDeclare a variable as max_val and set it with arr[size - 1] + 1. Start loop FOR from i to 0 till i less than size. Inside the loop, check IF i % 2 = 0 then set arr[i] to arr[i] + (arr[max] % max_val) * max_val and decrement the max by 1.

Can we change the starting index of an array?

It can never be assigned to. When used as a value it is automatically converted to a pointer to the first element, through which the array elements can be accessed and modified.


1 Answers

With mutating indices :(. Without looks hard (see stable in-place mergesort).

a = [8, 6, 7, 5, 3, 0, 9] indices = [3, 6, 2, 4, 0, 1, 5]  for i in xrange(len(a)):     x = a[i]     j = i     while True:         k = indices[j]         indices[j] = j         if k == i:             break         a[j] = a[k]         j = k     a[j] = x  print a 
like image 118
QWERTY Avatar answered Sep 24 '22 05:09

QWERTY