【递归】n个数的不重复排列

输入：

3

1 1 2

输出:

1 1 2

1 2 1

2 1 1

Delphi代码：

program unrepeat_permutation;
//不重复排列

const
  max_n = 10;

var
  n, m: integer;
  rcd, used, num: array[0..max_n] of integer;

procedure unrepeat_permutation(index: integer);
var
  i: integer;
begin
  if index = n then
  begin
    for i := 0 to n - 2 do
      Write(rcd[i], ' ');
    writeln(rcd[n - 1]);
    exit;
  end;

  for i := 0 to m - 1 do
    if used[i] > 0 then
    begin
      Dec(used[i]);
      rcd[index] := num[i];
      unrepeat_permutation(index + 1);
      Inc(used[i]);
    end;
end;

var
  i, j, val: integer;
begin
  while not seekeof do
  begin
    readln(n);
    m := 0;
    for i := 0 to n - 1 do
    begin
      Read(val);
      j := 0;
      while (j < m) do
      begin
        if val = num[j] then
        begin
          Inc(used[j]);
          break;
        end;
        Inc(j);
      end;
      if j = m then
      begin
        num[m] := val;
        used[m] := 1;
        Inc(m);
      end;
    end;
    unrepeat_permutation(0);
  end;
end.

C++代码：

#include <stdio.h>
#define MAX_N 10
int rcd[MAX_N], used[MAX_N], num[MAX_N];
int n,m;

void unrepeat_permutation(int index)
{
    int i;
    if (index == n)
    {
        for (i=0; i<n; i++)
        {
            printf("%d", rcd[i]);
            if (i<n+1)
            {
                printf(" ");
            }
        }
        printf("\n");
        return;
    }

    for (i=0; i<m; i++)
    {
        if (used[i]>0)
        {
            used[i]--;
            rcd[index] = num[i];
            unrepeat_permutation(index+1);
            used[i]++;
        }
    }
}

int read_data()
{
    int i,j,val;
    if (scanf("%d", &n) ==EOF)
    {
        return 0;
    }
    m=0;
    for (i=0; i<n; i++)
    {
        scanf("%d", &val);
        for (j=0; j<m; j++)
        {
            if (num[j]==val)
            {
                used[j]++;
                break;
            }
        }
        if (j==m)
        {
            num[m] = val;
            used[m++] = 1;
        }
    }
    return 1;
}

void main()
{
    while(read_data())
    {
        unrepeat_permutation(0);
    }
}