我需要一个简单的排列生成算法，它可以应用于简单的C语言。
5个回答
7
对数字进行排列组合：
为了使用每个排列组合，您需要连接到打印函数。
#include <stdio.h>
#include <stdlib.h>
/**
Read a number, N, from standard input and print the
permutations.
*/
void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++) {
printf("%4d", v[i] );
}
printf("\n");
}
} // print
void swap(int *v, const int i, const int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}
void rotateLeft(int *v, const int start, const int n)
{
int tmp = v[start];
for (int i = start; i < n-1; i++) {
v[i] = v[i+1];
}
v[n-1] = tmp;
} // rotateLeft
void permute(int *v, const int start, const int n)
{
print(v, n);
if (start < n) {
int i, j;
for (i = n-2; i >= start; i--) {
for (j = i + 1; j < n; j++) {
swap(v, i, j);
permute(v, i+1, n);
} // for j
rotateLeft(v, i, n);
} // for i
}
} // permute
void init(int *v, int N)
{
for (int i = 0; i < N; i++) {
v[i] = i+1;
}
} // init
int main()
{
int *v = (int*) malloc(sizeof(int)*10);
init(v, 10);
permute(v, 0, 10);
free(v);
}
- Ronny Brendel
2
7这是C ++代码，不是C。 但是，它可以轻松转换为C代码：
s / new int [10] / malloc（10*sizeof（int））/和s / delete [] v / free（v）/。 - Bart van Ingen Schenau3
全部
我在《计算机程序设计艺术》(TAOCP)中找到了一些按字典顺序生成排列的算法:
http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
按字典顺序生成 有许多方法可以系统地生成给定序列的所有排列[citation needed]。其中一种经典算法既简单又灵活，是基于按字典顺序查找下一个排列，如果存在的话。它可以处理重复值，对于这种情况，它仅生成不同的多重集合排列一次。即使对于普通排列，它也比按字典顺序生成Lehmer代码值(可能使用阶乘数系统)，并将其转换为排列要高效得多。使用它时，首先按(弱)递增顺序排序序列(这给出了它的按字典顺序最小的排列)，然后重复前进到下一个排列，只要找到一个排列就行。该方法可追溯到14世纪印度的Narayana Pandita，并经常被重新发现。
以下算法在给定排列之后按字典顺序生成下一个排列。它会直接更改给定的排列。
- 找到最大的索引k，使得a[k] < a[k + 1]。如果不存在这样的索引，则该排列是最后一个排列。
- 找到最大的索引l，使得a[k] < a[l]。由于 k+1 是这样一个索引，因此 l 是定义良好的，并且满足 k < l。
- 交换a[k]和a[l]。
- 反转从a[k + 1]到包括最后一个元素a[n]在内的序列。
执行第1步后，就知道位于位置k之后的所有元素都形成了一个弱递减序列，因此对这些元素的任何排列都不会使它按字典顺序前进；要前进，必须增加a[k]。第2步找到要替换a[k]的最小值a[l]，并在第3步中交换它们，将k之后的序列留在弱递减顺序中。然后，在第4步中反转此序列，即可产生其按字典顺序最小的排列，并获得整个序列初始状态的按字典顺序的后继状态。
- jeffjoy
2
这是一种经典算法，可以在《计算机程序设计艺术》等书籍中发现。
以下是一个我用于Project Euler问题的示例。它按字典顺序创建字符串的所有排列并将它们打印到stdout中。
#include<stdio.h>
int main()
{
char set[10]="0123456789";
char scratch;
int lastpermutation = 0;
int i, j, k, l;
printf("%s\n",set);
while (!lastpermutation)
{
//find largest j such that set[j] < set[j+1]; if no such j then done
j = -1;
for (i = 0; i < 10; i++)
{
if (set[i+1] > set[i])
{
j = i;
}
}
if (j == -1)
{
lastpermutation = 1;
}
if (!lastpermutation)
{
for (i = j+1; i < 10; i++)
{
if (set[i] > set[j])
{
l = i;
}
}
scratch = set[j];
set[j] = set[l];
set[l] = scratch;
//reverse j+1 to end
k = (9-j)/2; // number of pairs to swap
for (i = 0; i < k; i++)
{
scratch = set[j+1+i];
set[j+1+i] = set[9-i];
set[9-i] = scratch;
}
printf("%s\n",set);
}
}
return 0;
}
- Tristan
2
这是一个简单的递归解决方案，用于生成通过命令行传递的字符集的所有排列：
#include <stdio.h>
#include <string.h>
int perm(const char *src, int len, char *dest, char *destbits, int n) {
if (n == len) {
printf("%.*s\n", len, dest);
return 1;
} else {
int count = 0;
for (int i = 0; i < len; i++) {
if (destbits[i] == 0) {
destbits[i] = 1;
dest[n] = src[i];
count += perm(src, len, dest, destbits, n + 1);
destbits[i] = 0;
}
}
return count;
}
}
int main(int argc, char *argv[]) {
const char *src = (argc > 1) ? argv[1] : "123456789";
int len = strlen(src);
char dest[len], destbits[len];
memset(destbits, 0, sizeof destbits);
int total = perm(src, len, dest, destbits, 0);
printf("%d combinations\n", total);
return 0;
}
- chqrlie
1
我正在寻找更交互式的东西，然后实现我的较差版本。我可以看到一些优化，但现在它对我有所帮助。我希望这对任何人都有帮助。
#include <stdio.h>
#include <stdlib.h>
#define PERM_T int
#define PERM_T_PFLAG "%d"
void swap(PERM_T *array, int i, int j) {
PERM_T aux = array[i];
array[i] = array[j];
array[j] = aux;
}
void print_array_perm(PERM_T *array, int n) {
printf("[");
n -= 1;
for (int i = 0; i < n; i++) {
printf(PERM_T_PFLAG", ", array[i]);
}
if (n >= 0)
printf(PERM_T_PFLAG, array[n]);
printf("]\n");
}
void print_array_int(int *array, int n) {
printf("[");
n -= 1;
for (int i = 0; i < n; i++) {
printf("%d, ", array[i]);
}
if (n >= 0)
printf("%d", array[n]);
printf("]\n");
}
void copy_array_T(
PERM_T *src, PERM_T *dst,
int start, int end) {
for (int i = start; i < end; i++) {
dst[i] = src[i];
}
}
void copy_array_int(
int *src, int *dst,
int start, int end) {
for (int i = start; i < end; i++) {
dst[i] = src[i];
}
}
void rotate_array(
PERM_T *array,
int start, int end) {
PERM_T aux = array[start];
copy_array_T(
array + 1, array, start, end);
array[end - 1] = aux;
}
int factorial(int n) {
int result = 1;
while (n > 1) {
result *= n;
n--;
}
return result;
}
typedef struct {
PERM_T *data;
int length;
int *ks;
int kn;
int _i;
} Perm;
Perm perm_(
PERM_T *data, PERM_T *array, int n) {
copy_array_T(array, data, 0, n);
int kn = n > 1 ? n - 1 : 0;
int *ks = kn
? malloc(sizeof(PERM_T) * kn)
: NULL;
for (int i = 0; i < kn; i++)
ks[i] = i;
int max_iterations = factorial(n);
Perm p = {
.data = data,
.length = n,
.ks = ks,
.kn = kn,
._i = max_iterations
};
return p;
}
Perm perm(PERM_T *array, int n) {
PERM_T *data =
malloc(sizeof(PERM_T) * n);
return perm_(data, array, n);
}
Perm copy_perm(Perm p) {
Perm copy = perm(p.data, p.length);
copy_array_int(p.ks, copy.ks, 0, p.kn);
return copy;
}
void clear_perm(Perm* p) {
free(p->data);
if (p->kn) free(p->ks);
}
int completed_perm(Perm *p) {
return p->_i < 1;
}
void next_perm_self(Perm *p) {
int n = p->length;
if (completed_perm(p)) return;
p->_i--;
int k = p->kn - 1;
int *ks = p->ks;
PERM_T *data = p->data;
if (ks[k] + 1 != n) {
rotate_array(data, k, n);
ks[k] += 1;
} else {
while (k >= 0 && ks[k] + 1 == n) {
ks[k] = k;
rotate_array(data, k, n);
k -= 1;
}
if (k >= 0) {
rotate_array(data, k, n);
ks[k] += 1;
}
}
}
Perm next_perm_(Perm *p) {
Perm next = copy_perm(*p);
next_perm_self(&next);
return next;
}
Perm next_perm(Perm *p) {
Perm next = next_perm_(p);
clear_perm(p);
return next;
}
void print_perm(Perm p) {
print_array_perm(p.data, p.length);
}
void print_perm_(Perm p) {
printf("%p\n", p.data);
print_perm(p);
print_array_int(p.ks, p.kn);
}
Perm next_print(Perm *p) {
print_perm(p);
return next_perm(p);
}
void next_print_self(Perm *p) {
print_perm(*p);
next_perm_self(p);
}
int main() {
int a1[] = {1,2,3,4,5};
Perm p = perm(a1, 5);
int i = 0;
while (!completed_perm(&p)) {
printf("%3d ", i++);
// p = next_print(&p);
next_print_self(&p);
}
clear_perm(&p);
return 0;
}
- Daniel Farina
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接