c - 在C中寻找循环单转置 vector

Question

我将输入作为数组 A = [ 2,3,4,1]

输出只是 A 中元素的所有可能排列，可以通过单次换位(两个相邻元素的单次翻转)操作完成。所以输出是:

[3,2,4,1],[ 2,4,3,1],[2,3,1,4],[1,3,4,2]

允许循环转置。因此 [2,3,4,1] ==> [1,3,4,2] 是允许的并且是一个有效的输出。

如何在 C 中实现？

编辑在 python 中，它将按如下方式完成:

def Transpose(alist):
    leveloutput = []
    n = len(alist)
    for i in range(n):
        x=alist[:]
        x[i],x[(i+1)%n] = x[(i+1)%n],x[i]
        leveloutput.append(x)
    return leveloutput

Answer 1

此解决方案使用动态内存分配，这样您就可以为大小为 size 的数组执行此操作。

int *swapvalues(const int *const array, size_t size, int left, int right)
{
    int *output;
    int  sotred;

    output = malloc(size * sizeof(int));
    if (output == NULL) /* check for success */
        return NULL;
    /* copy the original values into the new array */
    memcpy(output, array, size * sizeof(int));
    /* swap the requested values */
    sotred        = output[left];
    output[left]  = output[right];
    output[right] = sotred;

    return output;
}

int **transpose(const int *const array, size_t size)
{
    int **output;
    int   i;
    int   j;

    /* generate a swapped copy of the array. */
    output = malloc(size * sizeof(int *));
    if (output == NULL) /* check success */
        return NULL;
    j = 0;
    for (i = 0 ; i < size - 1 ; ++i)
    {
        /* allocate space for `size` ints */
        output[i] = swapvalues(array, size, j, 1 + j);
        if (output[i] == NULL)
            goto cleanup;
        /* in the next iteration swap the next two values */
        j += 1;
    }
    /* do the same to the first and last element now */
    output[i] = swapvalues(array, size, 0, size - 1);
    if (output[i] == NULL)
        goto cleanup;
    return output;

cleanup: /* some malloc call returned NULL, clean up and exit. */
    if (output == NULL)
        return NULL;
    for (j = i ; j >= 0 ; j--)
        free(output[j]);
    free(output);

    return NULL;
}

int main()
{
    int array[4] = {2, 3, 4, 1};
    int i;
    int **permutations = transpose(array, sizeof(array) / sizeof(array[0]));
    if (permutations != NULL)
    {
        for (i = 0 ; i < 4 ; ++i)
        {
            int j;

            fprintf(stderr, "[ ");
            for (j = 0 ; j < 4 ; ++j)
            {
                fprintf(stderr, "%d ", permutations[i][j]);
            }
            fprintf(stderr, "] ");
            free(permutations[i]);
        }
        fprintf(stderr, "\n");
    }
    free(permutations);

    return 0;
}

虽然有些人认为 goto 是邪恶的，但这是一个很好的用途，不要用它来控制程序的流程(例如创建循环)，即令人困惑。但是对于一个在返回之前必须做几件事的函数的退出点，它认为它实际上是一个很好的用途，这是我的观点，对我来说它使代码更容易理解，我可能是错的。