Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
October 25th, 2011, 10:35 AM
 drew99
Contributing User

Join Date: Sep 2011
Posts: 31
Time spent in forums: 7 h 17 m 4 sec
Reputation Power: 2
Complex permutations of elements of an array

I have written two rotation functions that operate on a character array of length equal to a perfect square.
The first rotate n times each odd line to the right and n times each pair line to the left. The second rotates n times each odd column down and n times each pair column up, where n is the numer of current line or column.

Example:
abcde
fghij
klmno
pqrst
uvwxy

Becomes:
eabcd
hijfg
mnokl
tpqrs
uvwxy

And finally:
unoxd
epqcg
hvwfl
mabks
tijry

I would like to reduce everything to a single function, or rather, to a single loop that moves each character in its final position without performing all the steps.
You can do this? Any suggestions?

#2
October 25th, 2011, 11:24 AM
 leszek31417
Contributing User

Join Date: Jul 2011
Posts: 313
Time spent in forums: 1 Week 2 Days 18 h 56 m
Reputation Power: 0
Quote:
 Originally Posted by drew99 ... to a perfect square ...

Is there any other kind ?...

...

Show us some code.

But plz, use code tags ...

#3
October 25th, 2011, 12:02 PM
 drew99
Contributing User

Join Date: Sep 2011
Posts: 31
Time spent in forums: 7 h 17 m 4 sec
Reputation Power: 2
I've tried this:

Code:
```char txt[] = "abcdefghijklmnopqrstuvwxy";
int r = sqrt(strlen(txt));
char tmp[r][r];
int y, z, x = 0;

for(y = 0; y < r; y++)
{
for(z = 0; z < r - 1; z++)
{
if(((z + (y + 1)) % 2) == 1)
{
tmp[(r - (z + (y + 1)) - 1)][(z + (y + 1)) % r] = txt[x++];
}
else
{
tmp[(z + (y + 1) + 1) % r][(z + (y + 1)) % r] = txt[x++];
}
}
tmp[(y + 1) % r][(z + (y + 1)) % r] = txt[x++];
}```

It isn't correct, but I'm looking for something similar.

#4
October 25th, 2011, 11:33 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 3,458
Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 26 m 43 sec
Reputation Power: 403
I did not find a pattern.

Using executable Iverson notation I have found the ordered anagram index for several sizes of transformed matrices. I didn't see an obvious pattern. However, I've shown the work. If you see a pattern I'm sure I can direct you to the anagram index or cycle algorithms. I didn't examine odd sizes separately from even sizes.

My conclusion: you're well off using the two step process. I've used your algorithm implemented as row-rotations followed by row-rotations under transposition.

Code:
```   ]a=:5 5\$a.{~(a.i.'a')+i.25   NB. a is the alphabet
abcde
fghij
klmno
pqrst
uvwxy

_1 2 _3 4 _5|."0 1 a    NB. found: the correct rotation vector
eabcd
hijfg
mnokl
tpqrs
uvwxy

rotations=:(<:@:+:@:(2&|) * >:)@:i.@:#    NB. defined: a verb to compute the rotation vector

rotations a                    NB. it works
_1 2 _3 4 _5

drew99_transform=: ([ |."0 1&.|: |."0 1)~ rotations   NB. defined: a verb to apply the two rotations

drew99_transform a             NB. it works
unoxd
epqcg
hvwfl
mabks
tijry

coordinates 5          NB. coordinates generates this sort of a grid
┌───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│
├───┼───┼───┼───┼───┤
│3 0│3 1│3 2│3 3│3 4│
├───┼───┼───┼───┼───┤
│4 0│4 1│4 2│4 3│4 4│
└───┴───┴───┴───┴───┘

coordinates 8         NB.  a bigger grid
┌───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│0 5│0 6│0 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│1 5│1 6│1 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│2 5│2 6│2 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│3 0│3 1│3 2│3 3│3 4│3 5│3 6│3 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│4 0│4 1│4 2│4 3│4 4│4 5│4 6│4 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│5 0│5 1│5 2│5 3│5 4│5 5│5 6│5 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│6 0│6 1│6 2│6 3│6 4│6 5│6 6│6 7│
├───┼───┼───┼───┼───┼───┼───┼───┤
│7 0│7 1│7 2│7 3│7 4│7 5│7 6│7 7│
└───┴───┴───┴───┴───┴───┴───┴───┘

drew99_transform@:coordinates 5    NB. the transformation at the coordinate grid
┌───┬───┬───┬───┬───┐
│4 0│2 3│2 4│4 3│0 3│
├───┼───┼───┼───┼───┤
│0 4│3 0│3 1│0 2│1 1│
├───┼───┼───┼───┼───┤
│1 2│4 1│4 2│1 0│2 1│
├───┼───┼───┼───┼───┤
│2 2│0 0│0 1│2 0│3 3│
├───┼───┼───┼───┼───┤
│3 4│1 3│1 4│3 2│4 4│
└───┴───┴───┴───┴───┘

drew99_transform@:coordinates 8  NB. a larger example.  Does this help?
┌───┬───┬───┬───┬───┬───┬───┬───┐
│7 0│2 6│5 0│4 6│3 0│6 6│1 0│0 6│
├───┼───┼───┼───┼───┼───┼───┼───┤
│0 7│3 5│6 3│5 1│4 7│7 5│2 3│1 1│
├───┼───┼───┼───┼───┼───┼───┼───┤
│1 2│4 4│7 2│6 4│5 2│0 4│3 2│2 4│
├───┼───┼───┼───┼───┼───┼───┼───┤
│2 5│5 7│0 1│7 3│6 5│1 7│4 1│3 3│
├───┼───┼───┼───┼───┼───┼───┼───┤
│3 4│6 2│1 4│0 2│7 4│2 2│5 4│4 2│
├───┼───┼───┼───┼───┼───┼───┼───┤
│4 3│7 1│2 7│1 5│0 3│3 1│6 7│5 5│
├───┼───┼───┼───┼───┼───┼───┼───┤
│5 6│0 0│3 6│2 0│1 6│4 0│7 6│6 0│
├───┼───┼───┼───┼───┼───┼───┼───┤
│6 1│1 3│4 5│3 7│2 1│5 3│0 5│7 7│
└───┴───┴───┴───┴───┴───┴───┴───┘

(; ,) drew99_transform a     NB. ravel makes rank 1 vector  (displayed beside the example)
┌─────┬─────────────────────────┐
│unoxd│unoxdepqcghvwflmabkstijry│
│epqcg│                         │
│hvwfl│                         │
│mabks│                         │
│tijry│                         │
└─────┴─────────────────────────┘

i.2#3                        NB. create index matrix
0 1 2
3 4 5
6 7 8

i.2#6
0  1  2  3  4  5
6  7  8  9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35

(C.;A.),drew99_transform i.2#1        NB. cycle notation boxed beside anagram index of the drew99 transformation
┌───┬─┐
│┌─┐│0│
││0││ │
│└─┘│ │
└───┴─┘
(C.;A.),drew99_transform i.2#2        NB. for increasing sizes
┌─────────┬──┐
│┌─────┬─┐│12│
││2 1 0│3││  │
│└─────┴─┘│  │
└─────────┴──┘
(C.;A.),drew99_transform i.2#3
┌───────────────────┬──────┐
│┌───────┬───────┬─┐│273008│
││6 5 4 0│7 3 2 1│8││      │
│└───────┴───────┴─┘│      │
└───────────────────┴──────┘
(C.;A.),drew99_transform i.2#4
┌───────────────────────────────────────┬──────────────┐
│┌─────┬──────┬──────┬──────┬───────┬──┐│16589852909822│
││4 3 2│11 8 6│12 9 0│13 7 5│14 1 10│15││              │
│└─────┴──────┴──────┴──────┴───────┴──┘│              │
└───────────────────────────────────────┴──────────────┘
(C.;A.),drew99_transform i.2#5
┌──────────────────────────────────────────────────────────────────┬──────────────────────────┐
│┌──────────────────┬────────────┬────────────┬────────────────┬──┐│12760685818600938804433872│
││20 19 18 10 7 16 0│21 8 2 14 11│22 9 6 15 12│23 17 1 13 5 4 3│24││                          │
│└──────────────────┴────────────┴────────────┴────────────────┴──┘│                          │
└──────────────────────────────────────────────────────────────────┴──────────────────────────┘
(C.;A.),drew99_transform i.2#6
┌───────────────────────────────────────────────────────────────────────────────────────────────────  ┬──────────────────────────────────────────┐
│┌─────┬───────┬───────┬──────────┬────────┬───────┬────────┬───────┬────────┬──────────┬───────┬──┐  │314872672016634997710953315962608797582432│
││6 5 4│18 15 2│20 1 16│23 21 11 7│26 10 13│27 12 8│29 24 22│30 25 0│32 17 14│33 19 31 9│34 3 28│35││                                          │
│└─────┴───────┴───────┴──────────┴────────┴───────┴────────┴───────┴────────┴──────────┴───────┴──┘  │                                          │
└───────────────────────────────────────────────────────────────────────────────────────────────────  ┴──────────────────────────────────────────┘

NB. coordinates finds the base y representation of the index vector 0 to (y^2)-1  These are individually boxed, and all of these are shaped into a y by y matrix.
coordinates                  NB. show definition of verb coordinates to anyone who looks to the end
2&# \$ 2&# <@#: i.@:*:
```

Last edited by b49P23TIvg : October 25th, 2011 at 11:36 PM. Reason: detail

#5
October 26th, 2011, 01:01 AM
 leszek31417
Contributing User

Join Date: Jul 2011
Posts: 313
Time spent in forums: 1 Week 2 Days 18 h 56 m
Reputation Power: 0
Just some related remark:

Assume we flip ALL rows and then ALL columns.
Then this is equivalent to rotation by 180 degrees.
Such a rotation is simple, because sin=0 and cos=-1.

E.g. for 3x3 matrix we need only 4 swaps.
For 4x4 only 8 etc.

#6
October 26th, 2011, 02:40 AM
 LaughingBelly
Who set my Title?

Join Date: Jun 2004
Posts: 716
Time spent in forums: 3 Weeks 6 h 21 m 7 sec
Reputation Power: 256
I dont have a C/C++ compiler handy on this machine, but the problem presented is a straight forward computation. This code is written quickly in my browser. You will note that each char is moved only once to its final destination.

Code:
```<script>
var strz = new Array(new Array('a','b','c','d','e'),
new Array('f','g','h','i','j'),
new Array('k','l','m','n','o'),
new Array('p','q','r','s','t'),
new Array('u','v','w','x','y'));

var stry = new Array(new Array('a','b','c','d','e'),
new Array('f','g','h','i','j'),
new Array('k','l','m','n','o'),
new Array('p','q','r','s','t'),
new Array('u','v','w','x','y'));

for(i=0;i<strz.length;i++)
for(j=0;j<strz[i].length;j++)
{
destcol = ((j + strz[i].length + (((i+1)%2) -(i%2))*(i+1))%strz[i].length);
destrow = ((i + strz.length + (((destcol+1)%2)-(destcol%2))*(destcol+1))%strz.length);
stry[destrow][destcol] = strz[i][j];
}

</script>```
b49P23TIvg agrees!
__________________
Nobody is perfect. I am Nobody.

#7
October 26th, 2011, 10:27 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 3,458
Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 26 m 43 sec
Reputation Power: 403
perfect

nice work, belly laugh.
Your solution doesn't work "in place", but then, that's often a silly requirement these days.

Last edited by b49P23TIvg : October 26th, 2011 at 10:31 AM.

#8
October 28th, 2011, 09:11 AM
 drew99
Contributing User

Join Date: Sep 2011
Posts: 31
Time spent in forums: 7 h 17 m 4 sec
Reputation Power: 2
It works. Thanks a lot to all for you help.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Complex permutations of elements of an array