Evil Algorithm, applying transformation vector in-place?

Got questions? Got answers? Go here for both.

Moderator: MaxCoderz Staff

Post Reply
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Evil Algorithm, applying transformation vector in-place?

Post by King Harold »

This is quite annoying, and google isn't cooperating.

Suppose we have an array of data, called "data", and an array of incides called "indices" (very original..)
All indices [0 .. n-1] are present, and only once.

The array "result" is such that for every n, result[n] equals data[indices[n]].

Can the result be generated without copying the items of "data" into a new array? If so, how?
In other words, can "data" be modified in-place to have the property of "result"? (of course in that case the "data" used at the right hand side is taken from the old array, but that's just a technicality)

I really feel like it ought to be possible..
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Evil Algorithm, applying transformation vector in-place?

Post by benryves »

I can't think of any way that wouldn't require some additional storage where the amount of storage relates to the number of elements, sorry. :(
User avatar
calc84maniac
Regular Member
Posts: 112
Joined: Wed 18 Oct, 2006 7:34 pm
Location: The ex-planet Pluto
Contact:

Re: Evil Algorithm, applying transformation vector in-place?

Post by calc84maniac »

What language? Methinks you failed to specify...
~calc84maniac has spoken.

Projects:
F-Zero 83+
Project M (Super Mario for 83+)
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: Evil Algorithm, applying transformation vector in-place?

Post by King Harold »

Doesn't matter, all I need it an algorithm
But, please don't use that as an excuse to use something exotic ;)

edit: ok, Universe, you have won. Until I find a better way, I will just copy all data to a secondary array. :(
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Re: Evil Algorithm, applying transformation vector in-place?

Post by CoBB »

King Harold wrote:Doesn't matter, all I need it an algorithm
But, please don't use that as an excuse to use something exotic ;)

edit: ok, Universe, you have won. Until I find a better way, I will just copy all data to a secondary array. :(
http://www.jjj.de/fxt/

Have a look at the permutation functions of the lib, you might find something. Or just google for in-place permutation algorithms...
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: Evil Algorithm, applying transformation vector in-place?

Post by King Harold »

Cool! thanks :)
Post Reply