数列並び替え
Posted: 2013年11月27日(水) 13:04
C言語で１から順にnまで並んだ数列をn!通りに並び替え、出力させる方法はありますか？
例えばn=3のときは
123
132
213
231
312
321
です。
例えばn=3のときは
123
132
213
231
312
321
です。
あると思います．
とりあえず実直にループして羅列してみては？
#include <stdio.h>
int next(int a[], int n)
{
int i, j, k, t;
for (i = n - 1; ; ) {
j = i--;
if (a[i] < a[j]) {
for (k = n; a[i] >= a[--k]; ) ;
t = a[i], a[i] = a[k], a[k] = t;
while (j < --n) t = a[j], a[j++] = a[n], a[n] = t;
return 1;
}
if (i == 0) return 0;
}
}
int main()
{
int a[] = { 1, 2, 3 }, i, n = 3;
do {
for (i = 0; i < n; i++) printf(" %d", a[i]);
putchar('\n');
} while (next(a, n));
return 0;
}
今度は自分で考えてみました。かずま さんが書きました:C++ の next_permutation のコードをパクってきました。
#include <stdio.h>
int a[] = { 1, 2, 3 };
int n = 3;
void proc(int k)
{
int i, j, t;
if (k < n)
for (i = k; i < n; i++) {
t = a[i];
for (j = i; j > k; j--) a[j] = a[j-1];
a[k] = t;
proc(k+1);
t = a[k];
for (j = k; j < i; j++) a[j] = a[j+1];
a[i] = t;
}
else {
for (i = 0; i < n; i++) printf(" %d", a[i]);
putchar('\n');
}
}
int main(void)
{
proc(0);
return 0;
}
#include <stdio.h>
int n = 3, a[16], f[16];
void proc(int k)
{
int i;
if (k == n) {
for (i = 0; i < n; i++) printf(" %d", a[i] + 1);
putchar('\n');
} else
for (i = 0; i < n; i++)
if (!f[i])
a[k] = i, f[i] = 1, proc(k + 1), f[i] = 0;
}
int main(void) { proc(0); return 0; }
かずま さんが書きました:printf(" %d", a + 'A'); なんていうもの面白いかもしれません。
#include <stdio.h>
#define N 3
/* {1,2,3} -> ... -> {3,2,1} */
int next_permutation(int arr[],int n) {
int target;
int i;
int temp;
int* arr2;
int n2;
for(i=n-2;i>=0;i--) {
if(arr[i]<arr[i+1])break;
}
if(i<0)return 0;
target=i;
/* inline reverse_arr */
arr2=arr+target+1;
n2=n-target-1;
for(i=0;n2-i-1>i;i++) {
int t;
t=arr2[i];
arr2[i]=arr2[n2-i-1];
arr2[n2-i-1]=t;
}
for(i=target+1;i<n;i++) {
if(arr[i]>arr[target])break;
}
temp=arr[i];
arr[i]=arr[target];
arr[target]=temp;
return 1;
}
int main(void) {
int sequence[N];
int i;
for(i=0;i<N;i++)sequence[i]=i+1;
do {
for(i=0;i<N;i++)printf("%d%c",sequence[i],i+1<N?' ':'\n');
} while(next_permutation(sequence,N));
return 0;
}