-
Permutation problem
So currently I have a function that permutes a given word, for example:
If you input CAT, it gives you
CAT
CTA
ACT
ATC
TCA
TAC
Here's the function:
Code:
void RecursivePermute(char str[], int k) {
int j;
// Base-case: Since all letters are fixed, we can ONLY print
// what's stored in str.
if (k == strlen(str))
printf("%s\n", str);
else {
// Loop through each possible starting letter for index k,
// the first index for which we have a choice.
for (j=k; j<strlen(str); j++) {
// Place the character stored in index j in location k.
ExchangeCharacters(str, k, j);
// Print out all of the permutations with that character
// just chosen above fixed.
RecursivePermute(str, k+1);
// Put the original character that used to be there back
// in its place.
ExchangeCharacters(str, j, k);
}
}
}
// Pre-condition: str is a valid C String and i and j are valid indexes
// to that string.
// Post-condition: The characters at index i and j will be swapped in
// str.
void ExchangeCharacters(char str[], int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
I also have 2 arrays of numbers that look something like:
3 8 2
5 9 1
3 4 7
6 2 8
2 6 3
8 4 2
The top array rows represent 3 guys and the columns represent how they rated 3 girls. And vice versa for the bottom.
So:
Code:
[Girl 0] [Girl 1] [Girl 2]
[Guy 0] 4 8 7
[Guy 1] 6 7 5
[Guy 2] 5 9 6
[Guy 0] [Guy 1] [Guy 2]
[Girl 0] 7 6 8
[Girl 1] 6 5 9
[Girl 2] 4 7 3
Now comes the fun part. I need to get that function to permute an array of numbers, for example:
Starting array:
0 1 2 <-Indexes (Represent a guy)
0 1 2 <- Values (Represent a girl)
Permutations:
0 1 2
0 1 2
0 1 2
0 2 1
0 1 2
1 2 0
0 1 2
1 0 2
0 1 2
2 0 1
0 1 2
2 1 0
And after each permutation I need to somehow get those pairs to refer back to the array and add the lowest of the ratings for each pair. The second permutation for example:
[0][0] = Guy 0 & Girl 0 = 4
[1][2] = Guy 1 & Girl 2 = 5
[2][1] = Guy 2 & Girl 1 = 9
4 + 5 + 9 = 18 <- Value I need to store
So to sum it up, I need to permute an array of numbers that correlate to spots in those arrays (indexes = guy ratings, permuted values = girl ratings).
I'm pretty much at a standstill with how to get that function to permute an array of numbers instead of a string of characters and how to get the permuted pairs to take their numbers and use them to refer to that certain spot on the other arrays and grab the lower score :/
Any help is appreciated, sorry this is so long :P
-
I'd use parallel arrays to organize the data. The key being that you can always find Bob's data, because it's using the same index number in the second array, as Bob has in the string array (of names), in the first array.
The number array can have as many "columns" of data, as you want. Think of it like a spreadsheet.
Code:
Adam 176543289 //more numbers here, as needed
Bob 754189326 // " " " " "
etc.
and not change them. Use auxiliary arrays of indexes, as needed to compute your data.
Best thing to do is work it out by hand with a simple example, until you know all the little steps you use to do it - and that's the basis for your pseudo code for the program.