如何通过移位然后撤消来排列数组元素？

Question

#include <iostream>
using namespace std;

void permute(int arr[],int len){
    //if(len==1) cout << arr[fixed];
    for(int i=0; i<len; i++){
        cout << arr[i] << " ";
        if(len==0) return;
        for(int j=i; j<len-1; j++){
            arr[j] = arr[j+1];
        }
        permute(arr, len-1);
        cout << endl;
    }
}

int main(){
    int n = 3;
    int arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    permute(arr, n);
}

我知道用于排列元素的代码的交换方法。我正在尝试实现这种方法，其中我打印得到的每个元素，然后将其后的所有元素移动到下面一个位置。

但正因为如此，整个数组本身发生了变化。

当我完成一次迭代时，如何取回之前的数组，就像我们通过取消交换交换的元素来获取数组一样。

Answer 1

根据 wohlstad 评论，保留原始数组的副本可以解决您的问题。 这是我的做法：

#include <iostream>
#include <string.h>
using namespace std;

void permute(int arr[], int len){
    int copy[len];
    for(int i=0; i<len; i++){
        cout << arr[i] << " ";
        if(len==1) return;
        memcpy(copy, arr, len*sizeof(int));
        for(int j=i; j<len-1; j++){
            arr[j] = arr[j+1];
        }
        permute(arr, len-1);
        memcpy(arr, copy, len*sizeof(int));
        cout << endl;
    }
}

int main(){
    int n = 3;
    
    int arr[n];
    cout << "Enter Values" << "\n";
    for(int i = 0; i < n;){
        arr[i] = cin.get();
        if (arr[i] != ' ' && arr[i] != '\n'){
            ++i;
        }
    }
    
    permute(arr, n);
}

我还更改了基本条件来检查

len == 1

，这是来自

tbxfreeware

评论：

在循环内部，

i

始终小于

len

。因此，由于

i

从

0

开始，因此语句

if(len==0) return;

是一个 nop

我还更改了将值输入到数组中的方式（因为问题中使用的值对我不起作用）。 这是代码的测试运行：

Enter Values
A B C
65 66 67
67 66

66 65 67
67 65

67 65 66
66 65

这在某种程度上给出了数组中的所有排列（但是第一次迭代之后的每次迭代，在给定的递归深度，似乎忘记了前面的字符）。

为了解决这个问题，我添加了另一个数组来存储整个排列，然后将其打印出来一次

len == 1

void permute(int arr[], int len, int permutation[], int depth){
    int copy[len];
    for(int i=0; i<len; i++){
        permutation[depth] = arr[i];
        if(len==1){
            for(int j = 0; j < depth + 1; ++j){
                cout << permutation[j] << ' ';
            }
            return;
        }
        memcpy(copy, arr, len*sizeof(int));
        for(int j=i; j<len-1; j++){
            arr[j] = arr[j+1];
        }
        permute(arr, len-1, permutation, depth + 1);
        memcpy(arr, copy, len*sizeof(int));
        cout << endl;
    }
}

其调用方式如下：

int permutation[n];
permute(arr, n, permutation, 0);

这是一个测试运行

Enter Values
A B C
65 66 67
65 67 66

66 65 67
66 67 65

67 65 66
67 66 65