This discussion is archived
9 Replies Latest reply: Apr 20, 2010 12:22 AM by jwenting RSS

All possible race outcomes

843853 Newbie
Currently Being Moderated
Hey,

This is my problem - I'm making a program that will print all possible outcomes of a race, given that ALL participants can be disqualified, and logically, that there can not be several same places.

Say that we have 2 competitors. My idea was/is to put all the options into an array razvrstitve = (1st place, 2nd place, disqualification, disqualification), and then print all the possible permutations of it. Problem is that it also considers all disqualifications to be separate, so it, will for example print out that "1st driver : disqualified (taking in razvrstitve[2]), 2nd driver: disqualified (razvrstitve[3])" and "1st driver : disqualified (taking in razvrstitve[3]), 2nd driver: disqualified (razvrstitve[2])", which is practically the same and shouldn't be printed out.

Output example(odstop means disqualification):

1. Voznik: 2. mesto 2. Voznik: odstop
1. Voznik: odstop 2. Voznik: odstop
1. Voznik: 1. mesto 2. Voznik: odstop
1. Voznik: odstop 2. Voznik: odstop
1. Voznik: 2. mesto 2. Voznik: odstop
1. Voznik: 1. mesto 2. Voznik: odstop
1. Voznik: odstop 2. Voznik: 1. mesto
1. Voznik: odstop 2. Voznik: 1. mesto
1. Voznik: 2. mesto 2. Voznik: 1. mesto
1. Voznik: odstop 2. Voznik: 2. mesto
1. Voznik: odstop 2. Voznik: 2. mesto
1. Voznik: 1. mesto 2. Voznik: 2. mesto


I've tried with creating new arrays and not "letting in" those elements, which's exact order has already been printed, but It's not working like it should :/

Anyway, here is my code (the one that prints out all permutations, including duplicates), so if anyone has any ideas or pointers of how I can do what I want it'd be greatly appreciated.

Regards,
Sumo
public class Naloga4 {
     
     public static void main(String[] args) {
        int mest = 0;     
          int stTekmovalcev = 2;     // number of competitors a.k.a 
          //how long permutations should be
        int N = 2*stTekmovalcev; // number of options, inluding disqualification of
        //possibly every participant          
        int[] razvrstitve = new int[N];     
        
        for (int i = 0; i < N; i++) { // creates an array with all options inside            
             if (i < stTekmovalcev) {
                  razvrstitve[i] = 0;
             } else {
                  razvrstitve[i] = mest+1;
                  mest++;
             }             
        }
        razvrsti(razvrstitve, razvrstitve.length, stTekmovalcev);     
    }
    private static void razvrsti(int[] razvrstitve, int n, int r) {     // prints out all possible permutations
        if (r == 0) {
               for (int i = n; i < razvrstitve.length; i++) {
                    String mesto = "";
                    if (razvrstitve[i] != 0) {
                         mesto = String.valueOf((int) razvrstitve) + ". mesto";
                    } else {
                         mesto = "odstop";
                    }
System.out.printf((i-n+1) + ". Voznik: " + mesto + " ");
               }
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
zamenjaj(razvrstitve, i, n-1);
razvrsti(razvrstitve, n-1, r-1);
zamenjaj(razvrstitve, i, n-1);
}
}

public static void zamenjaj(int[] razvrstitve, int i, int j) {     // swaps positions in the array
     // so all permutations can be made
int temp = razvrstitve[i];
razvrstitve[i] = razvrstitve[j];
razvrstitve[j] = temp;
}
}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
  • 1. Re: All possible race outcomes
    791266 Explorer
    Currently Being Moderated
    You do understand that it looks like your code if obfuscated to most of us. It would have been cetter if you had translated the code into English.
  • 2. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    Yes offcourse, commented a bit on what I thought was most relevant but I suppose I should translate it whole for easier understanding. Will do the translations tommorow.
  • 3. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    Here is the above code translated, if it helps:
    public class ResultsPermutations {
         
         public static void main(String[] args) {
            int setResult = 0;     
              int nrOfCompetitors = 2;     // number of competitors a.k.a 
              //how long permutations should be     
            int N = 2*nrOfCompetitors;      // number of options, including disqualification of
            // possibly every participant     
            int[] possibleresults = new int[N];     
            
            for (int i = 0; i < N; i++) {           // creates an array with all possible results  
                 if (i < nrOfCompetitors) {
                      possibleresults[i] = 0;
                 } else {
                      possibleresults[i] = setResult+1;
                      setResult++;
                 }             
            }
            enumerate(possibleresults, possibleresults.length, nrOfCompetitors);     
        }
        private static void enumerate(int[] possibleresults, int n, int r) {     // prints out all possible permutations
            if (r == 0) {
                   for (int i = n; i < possibleresults.length; i++) {
                        String place = "";
                        if (possibleresults[i] != 0) {
                             place = String.valueOf((int) possibleresults) + ". place";
                        } else {
                             place = "Disqualification";
                        }
    System.out.printf("Driver " + "#" + (i-n+1) + ": " + place + " ");
                   }
    System.out.println();
    return;
    }
    for (int i = 0; i < n; i++) {
    swapArray(possibleresults, i, n-1);
    enumerate(possibleresults, n-1, r-1);
    swapArray(possibleresults, i, n-1);
    }
    }

    public static void swapArray(int[] possibleresults, int i, int j) {          // swaps positions in the array
         // so all permutations can be made
    int temp = possibleresults[i];
    possibleresults[i] = possibleresults[j];
    possibleresults[j] = temp;
    }
    }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
  • 4. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    You cannot use the same array for pooling possible results and writing actual results because the zero or disqualification case consumes one slot in the array in a recursion step but the number of available results in the remaining steps must not decrease after a zero result step. So if you use another array for output and have the zero result only once in the possibleresults array, the code below should work. In that case, of course, the output array must be used instead of possibleresults in the base case (r==0).
            for (int i = 0; i < n; i++) {
                output[r] = possibleresults;
    if(i>0) {
    swapArray(possibleresults, output, i, n-1);
    enumerate(possibleresults, output, n-1, r-1);
    swapArray(possibleresults, output, i, n-1);
    }
    else {
    enumerate(possibleresults, output, n, r-1);
    }
    }
    The number of possible outputs grows in an interesting way. According to the On-Line Encyclopedia of Integer Sequences it equals the number of partial permutations of an n-set or the number of n X n binary matrices with at most one 1 in each row and column. Didn't know those have anything to do with driving races...                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
  • 5. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    Thanks for the input but changing that actually makes things even more messed up:

    Driver #1: Disqualification
    Driver #1: Disqualification
    Driver #1: Disqualification
    Driver #1: Disqualification
    Driver #1: Disqualification Driver #2: Disqualification
    Driver #1: Disqualification Driver #2: Disqualification
    Driver #1: Disqualification
    Driver #1: 1. place Driver #2: Disqualification
    Driver #1: 1. place Driver #2: Disqualification
    Driver #1: Disqualification
    Driver #1: 2. place Driver #2: Disqualification
    Driver #1: 2. place Driver #2: Disqualification

    I was thinking of creating permutations of size k (where k goes from 0 to N) and then adding N - k 0s to it and permuting the 0s with permutations of size k and printing them out on the way. I'm just not sure that using arrays would be a good way of doing that, because you can't dynamically change its size, or can you?
  • 6. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    You would be better off splitting your algorithm into two phases, both of which have widely known solutions:

    Create each selection of Q from N of your contestants. Those not selected are disqualified.

    Create each ordering of the Q selected contestants. This ordering is the position of the qualified contestants.
  • 7. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    Slo_Sumo wrote:
    Thanks for the input but changing that actually makes things even more messed up:
    I can reproduce your result by making two bugs in my code: First, I set N = 2*nrOfCompetitors and second, I run the printing loop from n to output.length. Using the correct values (N = nrOfCompetitors+1 and running the printing loop from 1 to output.length) I get the desired seven outcomes.
  • 8. Re: All possible race outcomes
    843853 Newbie
    Currently Being Moderated
    Sorry about the very late reply, but that seems to have fixed it perkele. Thanks!
  • 9. Re: All possible race outcomes
    jwenting Journeyer
    Currently Being Moderated
    have you taken into consideration the possibility of shared positions?
    2 contenders could well finish in exactly the same time, from your posts you seem to have not handled that?