Python 的 itertools.product 在 C 中

Question

Python 中有一个函数以这种方式运行：

itertools.product("abc", repeat = 2)

return如下：

("a", "a")
("a", "b")
("a", "c")
("b", "a")
("b", "b")
("b", "c")
("c", "a")
("c", "b")
("c", "c")

更改 repeat 变量将更改元组中返回的项目数。这怎么能用 C 写成 return 一个字符数组？（字符串数组）

更新：我现在有了我写的这个功能：

void cartesian(char *a, int al, char *b, int bl){
    int i, j;
    char c[al * bl][2];
    for(i = 0; i < al; i++){
        for(j = 0; j < bl; j++){
            c[(i * bl) + j][0] = *(a + i);
            c[(i * bl) + j][1] = *(b + j);
            printf("%c%c\n", *(a + i), *(b + j));
        }
    }
}

int main(){
    char a[] = "abc";
    char b[] = "ab";
    cartesian(a, strlen(a), b, strlen(b));
    return 0;
}

我如何更改此函数，使其可以接收一组 char 数组并生成笛卡尔积？数组可以包含任意数量的字符，并且可以有任意数量的数组

该函数应如下所示：

void cartesian(char *a, int l){
    /*Do cartesian*/
}

示例数组：

[
    ['a', 'b', 'c', '[=16=]'],
    ['a', 'b', 'c', '[=16=]'],
    ['a', 'b', 'c', '[=16=]']
]

（包括用于计算数组长度的空值）应该产生

[
    ['a', 'a', 'a'],
    ['a', 'a', 'b'],
    ['a', 'a', 'c'],
    ['a', 'b', 'a'],
    ['a', 'b', 'b'],
    ['a', 'b', 'c'],
    ['a', 'c', 'a'],
    ['a', 'c', 'b'],
    ['a', 'c', 'c'],
    ['b', 'a', 'a'],
    ['b', 'a', 'b'],
    ['b', 'a', 'c'],
    ['b', 'b', 'a'],
    ['b', 'b', 'b'],
    ['b', 'b', 'c'],
    ['b', 'c', 'a'],
    ['b', 'c', 'b'],
    ['b', 'c', 'c'],
    ['c', 'a', 'a'],
    ['c', 'a', 'b'],
    ['c', 'a', 'c'],
    ['c', 'b', 'a'],
    ['c', 'b', 'b'],
    ['c', 'b', 'c'],
    ['c', 'c', 'a'],
    ['c', 'c', 'b'],
    ['c', 'c', 'c'],
]

Answer 1

下面的 C 程序创建了 "abc".

所有可能的排列

#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

int main()
{
    char str[] = "abc";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

可能有一种更快的编码方法。运行时间 O(n*n!)。我后来才注意到您要的是笛卡尔积。但是可以通过类似的请求找到几个堆栈溢出条目。

Answer 2

这是根据您的规范的笛卡尔积的 C 实现。请注意，参数是 char **a，而不是 char *a，因为它是一个字符串数组。

这是 previous answer.

的变体

    void cartesian(char **a, unsigned int l)
    {
        unsigned int *indices = calloc(l, sizeof(int));
        unsigned int changed;
        do {
            unsigned int finished = 0;
            unsigned int i;
            changed = 0;
            /* Print the current tuple */
            for (i = 0; i < l; i++) {
                putchar(a[i][indices[i]]);
            }
            putchar('\n');
            /* Loop over the arrays in reverse order */
            for (i = l - 1; !changed && !finished; i--) {
                /* Increment */
                indices[i]++;
                if (a[i][indices[i]]) {
                    /* We moved to the next character */
                    changed = 1;
                }
                else {
                    /* End of string, so roll over */
                    indices[i] = 0;
                }
                finished = i == 0;
            }
        } while (changed);
        free(indices);
    }

Python 的 itertools.product 在 C 中

Python's itertools.product in C

c

python

cartesian-product