Thread: Permutation problem

  1. #1
    Registered User alpine's Avatar
    Join Date
    Oct 2010
    Posts
    6

    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
    Last edited by alpine; 02-25-2011 at 09:33 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Problem creating a recursive string permutation function
    By indigo0086 in forum C++ Programming
    Replies: 4
    Last Post: 10-10-2006, 10:09 AM