p******o
发帖数: 125 | 1 请问有没有比较好的办法？我能想到的只能用stack,然后把需要的信息都存起来。但是
很麻烦，
代码写出来也不好看。 | d****n
发帖数: 233 | 2 // test1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
void PrintArray(int *A, unsigned int N)
{
for (unsigned int i = 0; i < N; i++)
{
printf("%d ", A[i]);
}
printf("\r\n");
}
// This method print out an array iteratively.
// The idea behind this is:
// 1. Suppose we have a way to print out permutation for A[n-1].
// 2. For every permutation, insert the nth element between any of
// the n-1 elements will construct a new permuation
// F
【在 p******o 的大作中提到】
: 请问有没有比较好的办法？我能想到的只能用stack,然后把需要的信息都存起来。但是
: 很麻烦，
: 代码写出来也不好看。
| d****n
发帖数: 233 | 3 void IterativePrintPermutation2(int *A, unsigned int N)
{
int *controller = new int[N];
for (unsigned int i = 0; i < N; i++)
controller[i] = i;
while (1)
{
PrintArray(A, N);
int i = -1;
while (++i < N)
{
if (controller[i] == 0)
{
controller[i] = i;
Swap(A, i, 0);
}
else
{
Swap(A, i, controller[i]);
Swap(A,
【在 d****n 的大作中提到】
: // test1.cpp : Defines the entry point for the console application.
: //
: #include "stdafx.h"
: void PrintArray(int *A, unsigned int N)
: {
: for (unsigned int i = 0; i < N; i++)
: {
: printf("%d ", A[i]);
: }
: printf("\r\n");
| r**u
发帖数: 1567 | 4 check next_permute function in STL
【在 p******o 的大作中提到】
: 请问有没有比较好的办法？我能想到的只能用stack,然后把需要的信息都存起来。但是
: 很麻烦，
: 代码写出来也不好看。
| p******o
发帖数: 125 | 5 老大，我看了半小时，真没看懂。。。
能否加几句注释解释一下。
我去看看next_permutation。
【在 d****n 的大作中提到】
: void IterativePrintPermutation2(int *A, unsigned int N)
: {
: int *controller = new int[N];
: for (unsigned int i = 0; i < N; i++)
: controller[i] = i;
:
: while (1)
: {
: PrintArray(A, N);
:
| d****n
发帖数: 233 | 6 First, not sure if this is the fatest one. I did it for fun a while ago.
Hope no interviewer will ask such kind of question.
Hints:
Think about # of permutations for n size array is 1*2*3*...*(n-1)*n.
if you have permutations for 1,2,3,...(n-1). what you need to do is to
switch one of the element with the nth and repeat the permutation for length
(n-1). all the elements after (n-1)th will be untouched.
【在 p******o 的大作中提到】
: 老大，我看了半小时，真没看懂。。。
: 能否加几句注释解释一下。
: 我去看看next_permutation。
| r**u
发帖数: 1567 | 7 解释一下next_permute，其实就是按字符顺序输出，比如12345
先在的permutation是12345，下一个就是12354。
算法思路，怎么找下一个呢：
比如先在：13542，下一个是14235，
首先要从后往前找第一个pair，满足A[i]
被变大的。上面这例子里这pair是35, 542已经是最大的permutation了。
所以要找到3。如果找不到这中pair，那么已经是最大的permutation了，比如54321。
然后从后往前找一个比3大的数，swap(it, 3)。这例子里是swap(4, 3)。
这样的话permutation变大，但是不会变得太大, swap(5, 3)就不对了。
先在变成14532了，然后reserve 532，得到14235。
【在 p******o 的大作中提到】
: 老大，我看了半小时，真没看懂。。。
: 能否加几句注释解释一下。
: 我去看看next_permutation。
| x****r
发帖数: 99 | 8 这个算法我见过，很精妙哈哈
【在 r**u 的大作中提到】
: 解释一下next_permute，其实就是按字符顺序输出，比如12345
: 先在的permutation是12345，下一个就是12354。
: 算法思路，怎么找下一个呢：
: 比如先在：13542，下一个是14235，
: 首先要从后往前找第一个pair，满足A[i]: 被变大的。上面这例子里这pair是35, 542已经是最大的permutation了。
: 所以要找到3。如果找不到这中pair，那么已经是最大的permutation了，比如54321。
: 然后从后往前找一个比3大的数，swap(it, 3)。这例子里是swap(4, 3)。
: 这样的话permutation变大，但是不会变得太大, swap(5, 3)就不对了。
: 先在变成14532了，然后reserve 532，得到14235。
| p******o
发帖数: 125 | 9 这个很通俗易懂，而且还可以handle重复的。谢谢了。
【在 r**u 的大作中提到】
: 解释一下next_permute，其实就是按字符顺序输出，比如12345
: 先在的permutation是12345，下一个就是12354。
: 算法思路，怎么找下一个呢：
: 比如先在：13542，下一个是14235，
: 首先要从后往前找第一个pair，满足A[i]: 被变大的。上面这例子里这pair是35, 542已经是最大的permutation了。
: 所以要找到3。如果找不到这中pair，那么已经是最大的permutation了，比如54321。
: 然后从后往前找一个比3大的数，swap(it, 3)。这例子里是swap(4, 3)。
: 这样的话permutation变大，但是不会变得太大, swap(5, 3)就不对了。
: 先在变成14532了，然后reserve 532，得到14235。
| p******o
发帖数: 125 | 10 谢谢老大。
length
【在 d****n 的大作中提到】
: First, not sure if this is the fatest one. I did it for fun a while ago.
: Hope no interviewer will ask such kind of question.
: Hints:
: Think about # of permutations for n size array is 1*2*3*...*(n-1)*n.
: if you have permutations for 1,2,3,...(n-1). what you need to do is to
: switch one of the element with the nth and repeat the permutation for length
: (n-1). all the elements after (n-1)th will be untouched.
|
|
