1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pascal - permutation

  1. Dec 7, 2015 #1
    1. The problem statement, all variables and given/known data
    I should write a program that determines how many columns of a given matrix are a permutation. The user will input some number N <=20 which will be the size of our matrix NxN. Then he will input the individual elements of the matrix by rows. I need to find out how many columns are the permuation of 1,...,N (column can only contain those numbers in random order).

    Example:
    Input:
    3
    1 2 2
    3 1 1
    2 3 1
    Output:
    2

    2. Relevant equations


    3. The attempt at a solution
    I have written a code that works and should be usable. However I believe there should be more elegant solution to this.. Probably by using a function that will check each column of the matrix and determine if it is the desired permutation. If it is we will increase some variable "result" by one. I am not quite sure how to best check if the column is the given permutation.. probably by having some array prepared and always tick off the number we find in our column and if the numbers match the numbers 1,...,N we know it is a permutation? Anyway I am not quite sure if that is the best way to do it and I would appreciate your help. What do you think of the solution below and how can I actually write such a function? I have never really worked with functions and arrays.
    Thanks.

    Code (Text):
    program columnPerm;
    var A:array[1..20,1..20] of integer;
    var N,C,R,i,differ,count,total:integer;
    var correct:boolean;

    begin
       read(N);
       for R:=1 to N do
       begin
          for C:=1 to N do
          begin
             read(A[R,C]);
          end;
          readln;
       end;

       for C:=1 to N do
       begin
          count:=0;
          if A[1,C]< (N+1) then
             if A[1,C]>0
                then count:=(count+1);
                   for R:=2 to N do
                   begin
                      correct:=true;
                      differ:=0;
                      for i:=1 to (R-1) do
                      begin
                         if A[R,C] <> A[i,C] then
                            differ:=(differ+1);
                      end;

                      if differ <> (R-1) then correct:=false;
                         if (A[R,C] > N) or (A[R,C] < 1) then correct:=false;
                            if correct then count:=(count+1);
                   end;

       if count=N then total:=(total+1);
       end;

    write(total);

    end.
     
     
  2. jcsd
  3. Dec 7, 2015 #2

    RUber

    User Avatar
    Homework Helper

    If you start by saving your input matrix as a sorted (within columns) copy of itself, then you can do a 1 to 1 comparison of the columns, since you will have removed any permutations.

    A second option might be to use the fact that your ideal column will have only one of each number. You could do something to isolate the maximum occurrence of any number in a column. If this is not 1, then it cannot be a permutation of 1...N.
     
  4. Dec 7, 2015 #3
    Is there an easy way to sort the columns? Can't think of any. I feel like if I wanted to do that the code would be just as long as the one I have already written.
     
    Last edited: Dec 7, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Pascal - permutation
  1. Pascal problem (Replies: 1)

  2. Pascal programming (Replies: 1)

  3. Pascal - "nice numbers" (Replies: 21)

Loading...