博客

We consider permutations of the numbers 1,…, N

for some N. By permutation we mean a rearrangment of the

number 1,…,N. For example

2  4  5  1  7  6  3  8

is a permutation of 1,2,…,8. Of course,

1  2  3  4  5  6  7  8

is also a permutation of 1,2,…,8.

We can “walk around” a permutation in a interesting way and here

is how it is done for the permutation above:

Start at position 1. At position 1 we have 2 and so we go to

position 2. Here we find 4 and so we go to position 4. Here we find

1, which is a position that we have already visited. This completes

the first part of our walk and we denote this walk by (1 2 4 1). Such

a walk is called a cycle. An interesting property of such

walks, that you may take for granted, is that the position we revisit

will always be the one we started from!

Examples

Sample input 1:

8

2 4 5 1 7 6 3 8

Sample output 1:

4

1 2 4 1

3 5 7 3

6 6

8 8

Sample input 2:

8

1 2 3 4 5 6 7 8

Sample output 2:

8

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

原来permutation有这样的cycle的，很好玩。

下面程序带了个自制的输入输出int的处理。使用getc, putchar这些输入输出的确会快很多的。

#pragma once
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <stdio.h>
#include <iostream>
using namespace std;

namespace
{

int scanInt2()
{
	char c = getc(stdin);
	while (c < '0' || c > '9')
	{
		c = getc(stdin);
	}
	int num = 0;
	while ('0' <= c && c <= '9')
	{
		num = (num<<3) + (num<<1) + c - '0';
		c = getc(stdin);
	}
	return num;
}

void printInt(int n)
{
	int i = 0;
	char buffer[32] = {0};
	while (n)
	{
		buffer[i++] = n % 10 + '0';
		n /= 10;
	}
	//buffer[i] = '\0';
	//fputs(buffer, stdout);
	for (i--; i >= 0; i--)
	{
		fputc(buffer[i], stdout);
	}
}

}

int PermutaionCycles()
{
	const int n = scanInt2();
	int *A = new int[n+1];
	for (int i = 1; i <= n; i++)
	{
		A[i] = scanInt2();
	}
	vector<vector<int> > rs;
	vector<int> tmp;
	for (int i = 1; i <= n; i++)
	{
		if (A[i] != -1)
		{
			tmp.clear();
			int j = i;	
			while (tmp.size() < 2 || tmp.back() != i)
			{
				tmp.push_back(j);
				int t = j;
				j = A[j];
				A[t] = -1;
			}
			rs.push_back(tmp);
		}
	}
	printInt(rs.size());
	putc('\n', stdout);
	for (int i = 0; i < (int)rs.size(); i++)
	{
		for (int j = 0; j < int(rs[i].size()); j++)
		{
			printInt(rs[i][j]);
			putc(' ', stdout);
		}
		putchar('\n');
	}
	delete [] A;
	return 0;
}