The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages
> C Programming
|
Complex permutations of elements of an array
Discuss Complex permutations of elements of an array in the C Programming forum on Dev Shed.
Complex permutations of elements of an array C programming forum discussing all C derivatives, including C#, C++, Object-C, and even plain old vanilla C. These languages are low level languages, and used on projects such as device drivers, compilers, and even whole computer operating systems.
|
|
 |
|
|
|
|
Dev Shed Forums Sponsor:
|
|
|
October 25th, 2011, 10:35 AM
|
|
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?
|
October 25th, 2011, 11:24 AM
|
|
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 ...
|
October 25th, 2011, 12:02 PM
|
|
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.
|
October 25th, 2011, 11:33 PM
|
 |
Contributing User
|
|
|
|
|
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
|
October 26th, 2011, 01:01 AM
|
|
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.
|
October 26th, 2011, 02:40 AM
|
 |
Who set my Title?
|
|
|
|
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];
}
alert(stry);
</script>
__________________
Nobody is perfect. I am Nobody.
|
October 26th, 2011, 10:27 AM
|
|
Contributing User
|
|
|
|
|
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.
|
October 28th, 2011, 09:11 AM
|
|
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.
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
 Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
