k****f
发帖数: 3794 | 1 有没有只需要n阶乘交换，就可以找到所有的排列的算法？
这个排列数组里面，按出现的顺序排下来，
前后两个排列只相差2个位置。 |
g*********8
发帖数: 53 | 2 123
132
312
321
231
213
right? |
k****f
发帖数: 3794 | 3 有程序么？？
手动是可以排的
【在 g*********8 的大作中提到】
: 123
: 132
: 312
: 321
: 231
: 213
: right?
|
S*********g
发帖数: 5298 | |
r*********r
发帖数: 3195 | 5 simplest solution is via backtracking |
r****t
发帖数: 10904 | |
k****f
发帖数: 3794 | 7 http://marknelson.us/2002/03/01/next-permutation
next_perm产生的序列不是相差一个交换
仔细看看figure 2的第二个与第三个
需要两个交换才能做到的 |
b***e
发帖数: 1419 | 8 #include "stdio.h"
class Bit {
public:
int max;
int direction;
int value;
Bit* higherBit;
Bit(int max, Bit* higher);
bool inc();
void changeDirection();
};
Bit::Bit(int max, Bit* higher) {
this->max = max;
this->direction = 1;
this->value = 0;
this->higherBit = higher;
}
void Bit::changeDirection() {
this->direction = 1 - this->direction;
}
bool Bit::inc() {
switch(this->direction) {
case 1:
if (this->value < this->max) {
this->value++;
return true;
|
b***e
发帖数: 1419 | |
C*******n
发帖数: 56 | 10 想了解排列大部分算法,读读下面的文章:
Permutation Generation Methods by ROBERT SEDGEWlCK |
g*********8
发帖数: 53 | 11 could you explain your algorithm? thank you.
【在 b***e 的大作中提到】
: 这个就是传说中的九连环了。
|
b***e
发帖数: 1419 | 12 I am computing permutation from the permutation number. Taking a 9-
permutation as example, the permutation number is a 8 bit number where the
first bit is 2-based, second bit is 3-base, ..., the 8th bit is 9 based.
The semantics of a permutation number is that, the value of the i_th bit
means the the number of the numbers that are smaller than i and is
positioned after i in the permutation. There is a one-to-one mapping
between permutations and permutation numbers.
Then the rest is to comput
【在 g*********8 的大作中提到】
: could you explain your algorithm? thank you.
|
