在C中寻找循环单个转置向量
我有输入数组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
此解决方案使用动态内存分配，这样您就可以为大小的数组执行此操作。
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是邪恶的，但这是一个非常好用的，不要用它来控制程序的流程（例如创建循环），这是令人困惑的。 但是对于在返回之前必须做几件事的函数的退出点，它认为它实际上是一个很好用，我认为，对我来说它使代码更容易理解，我可能是错的。
看看我用一个例子写的代码：
void transpose() { int arr[] = {3, 5, 8, 1}; int l = sizeof (arr) / sizeof (arr[0]); int i, j, k; for (i = 0; i < l; i++) { j = (i + 1) % l; int copy[l]; for (k = 0; k < l; k++) copy[k] = arr[k]; int t = copy[i]; copy[i] = copy[j]; copy[j] = t; printf("{%d, %d, %d, %d}\n", copy[0], copy[1], copy[2], copy[3]); } }
样本输出：
{5, 3, 8, 1} {3, 8, 5, 1} {3, 5, 1, 8} {1, 5, 8, 3}
几点说明：
-
单个内存块比指针数组更受欢迎，因为它具有更好的局部性和更少的堆碎片;
-
循环转置只有一个，它可以单独完成，从而避免了每次迭代中模运算符的开销。
这是代码：
#include #include #include int *single_transposition(const int *a, unsigned int n) { // Output size is known, can use a single allocation int *out = malloc(n * n * sizeof(int)); // Perform the non-cyclic transpositions int *dst = out; for (int i = 0; i < n - 1; ++i) { memcpy(dst, a, n * sizeof (int)); int t = dst[i]; dst[i] = dst[i + 1]; dst[i + 1] = t; dst += n; } // Perform the cyclic transposition, no need to impose the overhead // of the modulo operation in each of the above iterations. memcpy(dst, a, n * sizeof (int)); int t = dst[0]; dst[0] = dst[n-1]; dst[n-1] = t; return out; } int main() {include int a[] = { 2, 3, 4, 1 }; const unsigned int n = sizeof a / sizeof a[0]; int *b = single_transposition(a, n); for (int i = 0; i < n * n; ++i) printf("%d%c", b[i], (i % n) == n - 1 ? '\n' : ' '); free(b); }
有许多方法可以解决这个问题，最重要的问题是：如何使用输出以及变量的大小是多少。 你已经说过arrays会非常大，因此我假设内存，而不是CPU将是这里最大的瓶颈。
如果输出将仅使用几次（特别是仅使用一次），那么最好使用function方法：动态生成每个转置，并且一次不要在内存中使用多个转置。 对于这种方法，许多高级语言可以起作用（有时甚至可能比C更好）。
如果数组的大小是固定的或半固定的（例如在编译时已知的几个大小），您可以使用C ++模板定义结构。
如果size是动态的并且你仍然希望在内存中进行每个转置，那么你应该分配一个巨大的内存块并将其视为连续的数组数组。 这在机器级别上非常简单明了。 不幸的是，它最好使用指针算法来解决，这是C / C ++的一个特性，它以难以理解而闻名。 （如果你从基础知识中学习C语，但是从高级语言中跳出来的人已经certificate了第一次完全错误的记录）其他方法是有大量指向较小数组的指针，这导致双指针**这对新人来说更可怕。
很抱歉这篇文章不是真正的答案，但恕我直言，有太多的问题需要选择最佳解决方案，我觉得你需要更多的C基础知识来自己管理它们。
/编辑：由于其他解决方案已经发布，这里是一个内存占用最少的解决方案。 这是最有限的方法，它反复使用相同的一个缓冲区，你必须确保你的代码在第一次转置时完成，然后再转到下一个。 从好的方面来说，当其他解决方案需要太字节的内存时，它仍然会正常工作。 它也是如此苛刻，以至于它可以用高级语言实现。 我坚持使用C ++，以防您希望一次拥有多个矩阵（例如，比较它们或同时运行多个线程）。
#define NO_TRANSPOSITION -1 class Transposable1dMatrix { private: int * m_pMatrix; int m_iMatrixSize; int m_iCurrTransposition; //transposition N means that elements N and N+1 are swapped //transpostion -1 means no transposition //transposition (size-1) means cyclic transpostion //as usual in C (size-1) is the last valid index public: Transposable1dMatrix(int MatrixSize) { m_iMatrixSize = MatrixSize; m_pMatrix = new int[m_iMatrixSize]; m_iCurrTransposition = NO_TRANSPOSITION; } int* GetCurrentMatrix() { return m_pMatrix; } bool IsTransposed() { return m_iCurrTransposition != NO_TRANSPOSITION; } void ReturnToOriginal() { if(!IsTransposed())//already in original state, nothing to do here return; //apply same transpostion again to go back to original TransposeInternal(m_iCurrTransposition); m_iCurrTransposition = NO_TRANSPOSITION; } void TransposeTo(int TranspositionIndex) { if(IsTransposed()) ReturnToOriginal(); TransposeInternal(TranspositionIndex); m_iCurrTransposition = TranspositionIndex; } private: void TransposeInternal(int TranspositionIndex) { int Swap1 = TranspositionIndex; int Swap2 = TranspositionIndex+1; if(Swap2 == m_iMatrixSize) Swap2 = 0;//this is the cyclic one int tmp = m_pMatrix[Swap1]; m_pMatrix[Swap1] = m_pMatrix[Swap2]; m_pMatrix[Swap2] = tmp; } }; void main(void) { int arr[] = {2, 3, 4, 1}; int size = 4; //allocate Transposable1dMatrix* test = new Transposable1dMatrix(size); //fill data memcpy(test->GetCurrentMatrix(), arr, size * sizeof (int)); //run test for(int x = 0; xTransposeTo(x); int* copy = test->GetCurrentMatrix(); printf("{%d, %d, %d, %d}\n", copy[0], copy[1], copy[2], copy[3]); } }