
Multiple values [was:] Re: scanf() type function
Quote:
> PPS: Incidentally I could have used Dylans integer division recently for
> transposing an (A x B) matrix to a (B x A) matrix in memory. I had to do it
> in C because Dylan was not an option. I did not manage to do it in-place.
> Does anyone know such an in-place algorithm?
Sure. Let's invent one :-)
First: you can't do it at all without *some* sort of additional storage --
it's just a question of how *much* additional storage.
Assuming you're allowed space to store one element (could be reduced to
one byte or one bit if you *really* insisted :-) ...
define method main(appname, #rest arguments)
let A = 3;
let B = 7;
let s = "abcdefgABCDEFG1234567";
for (root from 0 below A * B)
block (next-root)
// see if this char has already been swapped
let (row, col) = floor/(root, A);
let item = col * B + row;
while (item ~= root)
if (item < root) // this root must have already been on a cycle
next-root();
end;
let (row, col) = floor/(item, A);
item := col * B + row;
end;
// permute a cycle
format-out("saving %c at %d\n", s[root], root);
let tmp = s[root];
let (row, col) = floor/(root, A);
let item = col * B + row;
let prev = root;
while (item ~= root)
format-out("Copying %c from %d to %d\n", s[item], item, prev);
s[prev] := s[item];
prev := item;
let (row, col) = floor/(item, A);
item := col * B + row;
end;
s[prev] := tmp;
format-out("Putting saved item %c at %d %s\n", tmp, prev, s);
end;
end for;
format-out("Transposed = '%s'\n", s);
exit(exit-code: 0);
end method main;
./transpose
saving a at 0
Putting saved item a at 0 abcdefgABCDEFG1234567
saving b at 1
Copying A from 7 to 1
Copying C from 9 to 7
Copying d from 3 to 9
Putting saved item b at 3 aAcbefgCBdDEFG1234567
saving c at 2
Copying 1 from 14 to 2
Copying 5 from 18 to 14
Copying g from 6 to 18
Putting saved item c at 6 aA1befcCBdDEFG5234g67
saving e at 4
Copying B from 8 to 4
Copying 3 from 16 to 8
Copying F from 12 to 16
Putting saved item e at 12 aA1bBfcC3dDEeG52F4g67
saving f at 5
Copying 2 from 15 to 5
Putting saved item f at 15 aA1bB2cC3dDEeG5fF4g67
saving D at 10
Putting saved item D at 10 aA1bB2cC3dDEeG5fF4g67
saving E at 11
Copying 4 from 17 to 11
Copying 6 from 19 to 17
Copying G from 13 to 19
Putting saved item E at 13 aA1bB2cC3dD4eE5fF6gG7
saving 7 at 20
Putting saved item 7 at 20 aA1bB2cC3dD4eE5fF6gG7
Transposed = 'aA1bB2cC3dD4eE5fF6gG7'
If you don't mind using one bit of storage per array element, you can
avoid the first while loop by instead testing a bit vector to see if that
particular element has already been moved.
-- Bruce