1. Limited time only! Sign up for a free 30min personal 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).

    1 2 2
    3 1 1
    2 3 1

    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.

    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;

       for R:=1 to N do
          for C:=1 to N do

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

                      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);

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


  2. jcsd
  3. Dec 7, 2015 #2


    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