# Pascal - permutation

1. Dec 7, 2015

### tawi

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
for R:=1 to N do
begin
for C:=1 to N do
begin
end;
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. Dec 7, 2015

### RUber

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.

3. Dec 7, 2015

### tawi

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