[算法] 上市排列

九月 3, 2013 nguyenvanquan7826 算法 14 回复

我将建立程序将列出的排列 {1, 2, …, ñ} 为了解释.
例如，其中n = 3, 我列出足够 6 转变:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

这样将是第一置换<1, 2, …, N>. 置换最后<n的, N-1, …, 1>.

置换将诞生必须比当前排列更大, 订货时绰绰有余排列更多更大的意义上当前排列不能在它们之间的不同的排列. 假设当前排列为A = <3, 2, 6, 5, 4, 1>, 评测 4 最后一个元素, 我看到他们是降, 这意味着即使我们有置换 4 怎么这个元素, 我还可以得到多一点的排列当前排列. 因此，我们必须考虑[2] = 2, 用不同的值替换. 它将由值替换?, 不能 1 因为如果这样会更小排列, 不能 3 对于具有[1] = 3 已经 (元件之后，选择元件之前没有被选择为所述数值). 剩余价值 4, 5, 6. 因为他们需要一个更大的置换足够大的电流，所以我们选择[2] = 4. 也值 (该[3], 该[4], 该[5], 该[6]) 将在实践中 {2, 6, 5, 1}. 也因为够大的，所以我们会发现的最小的代表 4 分配给该号码[3], 该[4], 该[5], 该[6] 即<1, 2, 5, 6>. 因此，新的置换将是<3, 4, 1, 2, 5, 6>.

有通过这个例子任何评论: 当前排列的端部被降, 所以[5] = 4 在最后一段的最小数量下降较大满足以下条件：[2] = 2. 如果换一个[5] 为[2] 我将是一个[2] = 4 而最终还是要排序降序. 当它要代表最终的最小值，我们只是反向末段. 在情况下，电流排列是<2, 1, 3, 4>下一个排列是<2, 1, 4, 3>. 我们也可以考虑置换<2, 1, 3, 4>具有锥形端, 这包括结束 1 元素 (4) 因此，从目前的排列在下生物排列可以如下建:

  1. 确定最长的锥形端, 元件A I寻找索引[在] 晚启动. 这意味着从结束位置查找范围高达第二元件 2 (因为如果你看看这是你最后的排列的第一个元素，那么就没有必要), 具有：i满足第一索引[I-1] < 该[在].
  2. 如果发现上述指标i
    – 在锥形端, 找到元素[到] 大多数小到满足条件的[到] > 该[I-1]. 由端部的锥形, 这从第一行的末尾搜索上遇到的第索引k满足完成[到] > 该[I-1] (可以使用二进制搜索).
    – 岛值得一[到] 和[I-1]
    – 为了推翻锥形端 (从[在] 到[到]) 成为上升.
  3. 如果你没有找到的整个范围，即约降, 下面是最终配置.

C ++代码说明.

/*
code by nguyenvanquan7826
*/

#include <cstdio> 
#include <cstdlib>
#include <iostream>
#include <algorithm>		// thu vien chua ham swap (hoan vi 2 so)
using namespace std;

int main(int argc, char **argv)
{
	int n, *a;
	scanf("%d", &n);
	a = new int[n];
	for (int i=0; i<n; i++)			// khoi tao va in ra cau hinh ban dau
	{
		a[i] = i+1;
		printf("%d   ", a[i]);
	}	
	printf("n");
	
	int i = n-1;		// i la vi tri ma doan cuoi giam dan
	while (i>0)			// trong khi doan cuoi khong phai bat dau tu vi tri dau tien
	{
		i = n-1;
		while (a[i] < a[i-1])	// tim vi tri dau tien ma doan cuoi giam dan
		{
			i--; 
		}
		
		if (i>0)		// Neu tim duoc i
		{
			int k;		// tim so a[k] nho nhat trong doan giam dan ma a[k] > a[i-1]
			for (k = n-1; k >= i; k--)		
			{
				if (a[k] > a[i-1])		
				{
					break;
				}
				
			}
			swap(a[k], a[i-1]);		// hoan vi a[k] va a[i-1]
			
			// dao nguoc doan cuoi giam dan thanh tang dan
			for (int k = i; k < i + (n - i) / 2; k++)	
			{
				swap(a[k], a[n - 1 - k + i]);
			}
			
			for (int k = 0; k < n; k++)		// in hoan vi ra
			{
				printf("%d   ", a[k]);
			}
			printf("n");
		}
	}
	
	return 0; 
}

文章转引自 课程数据结构和勒·明晃老师的算法. 你可以看到代码帕斯卡尔因为他在教学大纲中写道.