Переменное количество итераций вложенного массива в C

Вы можете сделать это, создав некоторые данные, которые будут действовать как итератор, и рассматривать их как одну итерируемую вещь. Эти данные будут содержать отдельный счетчик для каждого измерения, которое вы хотите обработать, и они будут инициализироваться, тестироваться и увеличиваться с помощью функций, которые сами выполняют итерацию по каждому измерению. Вот пример использования простого массива для счетчиков.

#include <string.h>


//  Initialize counters to zero.
static void InitializeCounters(long N, long *Counters)
{
    memset(Counters, 0, N * sizeof *Counters);
}


//  Return true if there are more values to iterate, false otherwise.
static _Bool MoreToIterate(long N, long *Counters, const long End)
{
    return Counters[0] < End;
}


//  Increment the counters, lexicographic (dictionary/odometer) style.
static void IncrementCounters(long N, long *Counters, const long End)
{
    /*  Increment each dimension (except the first will be special).  If it
        rolls over its end, reset it to zero and go on the next dimension.
        If it does not roll over, stop there.
    */
    for (long i = N-1; 0 < i; --i)
        if (++Counters[i] < End)
            return;
        else
            Counters[i] = 0;

    /*  For dimension zero, do not reset it, so MoreToIterate can see it
        finished.
    */
    ++Counters[0];
}


#include <stdio.h>
#include <stdlib.h>


static void _Noreturn Usage(char *argv[])
{
    fprintf(stderr, "Usage: %s <number of elements per group>\n", argv[0]);
    exit(EXIT_FAILURE);
}


//  Define the set of items to draw from.
char Population[] = { 'a', 'b', 'c', 'd' };
#define ElementCount    (sizeof Population / sizeof *Population)


int main(int argc, char *argv[])
{
    //  Parse argument.

    if (argc != 2)
        Usage(argv);

    char *end;
    long ElementsPerGroup = strtol(argv[1], &end, 0);
    if (*end != '\0')
        Usage(argv);

    if (ElementsPerGroup < 0)
        Usage(argv);

    //  Allocate one counter for each element in a group.
    long *Counters = malloc(ElementsPerGroup * sizeof *Counters);
    if (!Counters)
    {
        fprintf(stderr, "Error, unable to allocate memory.\n");
        exit(EXIT_FAILURE);
    }

    /*  Use a traditional for loop to initialize the counters, test whether
        we are done, and increment the counters.
    */
    for (   InitializeCounters(ElementsPerGroup, Counters);
            MoreToIterate(ElementsPerGroup, Counters, ElementCount);
            IncrementCounters(ElementsPerGroup, Counters, ElementCount))
    {
        //  Print the elements in the curerent group.
        for (long i = 0; i < ElementsPerGroup; ++i)
            printf("%c ", Population[Counters[i]]);
        printf("\n");
    }

    free(Counters);
}

Есть несколько способов сделать это. Некоторые используют рекурсию, другие управляют индексами цикла с помощью дополнительных структур.

Вот пример того, как я это сделал без рекурсии:

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    n += 1;
    char arr[n];
    for(int i=0; i<n; ++i){
        arr[i] = 'a' + i;
    }

    int count[n];
    for(int i=0; i<n; ++i){
        count[i] = 0;
    }

    while( count[0] == 0 ){
        
        for(int i=1; i<n; ++i){
            printf("%c ", arr[count[i]]);
        }
        printf("\n");

        for(int i=n-1; i>=0; --i){
            if (count[i] == n-2){
                count[i] = 0;
            } else {
                count[i] += 1;
                break;
            }
        }
    }
}

Я думаю, код можно легко улучшить, но, по крайней мере, он функционален. Идея состоит в том, чтобы перебрать все возможные перестановки, сохраняя текущий индекс элемента для каждого «ранга» в другой структуре.

Я добавляю дополнительный ранг в начале, чтобы обнаружить переполнение после обработки всех перестановок.

Я сделал это с помощью рекурсии :-)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define SYMBOLS "hu4-"
 
void recurse(char *x, int currlevel, int maxlevel) {
    if (currlevel == maxlevel) {
        // last level
        printf("%s\n", x);
    } else {
        // add one level
        for (int k = 0; k < strlen(SYMBOLS); k++) {
            x[currlevel] = SYMBOLS[k];
            recurse(x, currlevel + 1, maxlevel);
        }
    }
}
 
int main(void) {
    int loops = 5;
    char *x = calloc(loops + 1, 1); // assume OK
    recurse(x, 0, loops);
    free(x);
    return 0;
}

Смотрите https://ideone.com/38ThQ5

Это код, который я в итоге использовал, очень похож на ответ @PoneyUHC.

#include <stdio.h>  /* printf(), putchar() */
#include <stdlib.h> /* calloc(), free() */

#define ARR_SZ 4

int main(void) {
    int arr[ARR_SZ] = { 'a', 'b', 'c', 'd' };

    /* This would be the run-time nesting level. Change it to see the
     * difference. */
    const int max_nesting = 3;
    int* indexes = calloc(max_nesting, sizeof(int));

    /* While the outer-most loop isn't done */
    while (indexes[0] < ARR_SZ) {
        /* This would be the body of the innermost loop. It can access all the
         * loop counters by traversing the `indexes' array. */
        for (int i = 0; i < max_nesting; i++)
            printf("%c ", arr[indexes[i]]);
        putchar('\n');

        /* Increase necessary counters from the inner-most to the outer-most */
        for (int cur_idx = max_nesting - 1; cur_idx >= 0; cur_idx--) {
            if (cur_idx == 0 || indexes[cur_idx] + 1 < ARR_SZ) {
                indexes[cur_idx]++;
                break;
            }

            indexes[cur_idx] = 0;
        }
    }

    free(indexes);
    return 0;
}

Что, если вместо пар я захочу напечатать все возможные группы по 3? Конечно, я мог бы и дальше добавлять вложенные циклы, но что, если количество элементов в этих «группах» неизвестно до момента выполнения?

C++ имеет std::next_permutation в алгоритме заголовка, который делает нечто подобное. Но здесь используется понятие перестановки без повторений. И использует итераторы, C++ штука.

Я покажу способ реализовать это в C как

    int   so_next_permutation(Perm*, const char* msg);

Идея та же, что и у C++next_permutation: функция возвращает 0, когда перестановок больше нет, или возвращает 1 после вывода следующей перестановки на стандартный вывод. Perm — это простой struct, абстрагирующий управление итерациями. Используются две вспомогательные функции:

• Perm* so_create_perm( size_t sample, size_t size, void** source, int (*show)(void**, size_t));
• Perm* so_destroy_perm(Perm*);

Аргументы говорят сами за себя:

• размер выборки: общее количество элементов в каждой перестановке

• размер: общее количество элементов в массиве

• show — функция, умеющая отображать один элемент (не перестановку)

  Я покажу два примера. Полный код находится в конце.

Это работает, возможно, для любого типа массива или структуры и для любого размера выборки.

Пример 1

Здесь используется массив из исходного вопроса.
Пользователь должен указать функцию show, например:

    int show_one(void**, size_t);

В этом случае это может быть так же просто, как

int show_one(void** source, size_t pos)
{   if (source == NULL) return -1;
    char* p = (char*)source;
    printf("%c", p[pos]);
    return 0;
}

Причина этого в том, чтобы иметь универсальный next_permutation, который работает для любого содержимого массива. Программа просто вызывает next_permutation, пока не вернется 0. Код здесь просто печатает следующую перестановку, но его можно легко изменить, чтобы вернуть строку с перестановкой.

int main(int argc, char* argv[])
{
    size_t size = 1;
    if (argc > 1) size = atoi(argv[1]);
    char  my_test[] = {'a', 'b', 'c', 'd'};
    size_t n_items   = sizeof(my_test) / sizeof(my_test[0]);
    Perm*  p         = so_create_perm(
        size, n_items, (void**)my_test, show_one);
    size_t count   = 0;
    char   msg[20] = {0};
    do {
        count += 1;
        sprintf(msg, "\t\t#%04d ", (int)count);
    } while (so_next_permutation(p, msg) != 0);
    p = so_destroy_perm(p);
    fprintf(
        stderr,
        "\n\t%llu perm. (with "
        "repetition) of size %llu. Set of %llu "
        "items. \n",
        count, size, n_items);
    return 0;
};

Использование простое: при вызове без аргументов он будет принимать только один элемент для каждой перестановки, просто перечисляя элементы. Или пользователь может установить размер выборки в качестве аргумента.

выход 1

Ниже мы видим результаты для некоторых размеров выборки.

SO > v0
                #0001 [ a ]
                #0002 [ b ]
                #0003 [ c ]
                #0004 [ d ]

        4 perm. (with repetition) of size 1. Set of 4 items.

SO > v0 2
                #0001 [ a, a ]
                #0002 [ b, a ]
                #0003 [ c, a ]
                #0004 [ d, a ]
                #0005 [ a, b ]
                #0006 [ b, b ]
                #0007 [ c, b ]
                #0008 [ d, b ]
                #0009 [ a, c ]
                #0010 [ b, c ]
                #0011 [ c, c ]
                #0012 [ d, c ]
                #0013 [ a, d ]
                #0014 [ b, d ]
                #0015 [ c, d ]
                #0016 [ d, d ]

        16 perm. (with repetition) of size 2. Set of 4 items.

SO > v0 4
                #0001 [ a, a, a, a ]
                #0002 [ b, a, a, a ]
                #0003 [ c, a, a, a ]
 // truncated...
                #0255 [ c, d, d, d ]
                #0256 [ d, d, d, d ]

        256 perm. (with repetition) of size 4. Set of 4 items.

SO >

Пример 2

Здесь используется массив строк. Пользователю просто нужно написать новую show функцию, которая делает ожидаемое.
В примере используется этот простой:

int show_one(void** source, size_t pos)
{
    if (source == NULL) return -1;
    const char** array = (const char**)source;
    printf("\"%s\"", array[pos]);
    return 0;
}

Вот код maim (полный компилируемый код находится в конце)

int main(int argc,char** argv)
{
    size_t size = 1;
    if (argc > 1) size = atoi(argv[1]);
    const char* my_test[] = {
        "10", "Joker", "Queen", "King", "Ace"};
    size_t n_items = sizeof(my_test)/sizeof(my_test[0]);
    Perm*        p = so_create_perm(
        size, n_items,
        (void**)my_test, show_one);
    size_t count   = 0;
    char         msg[20] = {0};
    do {
        count += 1;
        sprintf(msg, "\t\t#%04d ", (int)count);
    } while (so_next_perm(p, msg) != 0);
    p = so_destroy_perm(p);
    fprintf(
        stderr,
        "\n\t%llu perm. (with "
        "repetition) of size %llu. Set of %llu "
        "items. \n",
        count, size, n_items);
    return 0;
};

выход 2

SO > v1
                #0001 [ "10" ]
                #0002 [ "Joker" ]
                #0003 [ "Queen" ]
                #0004 [ "King" ]
                #0005 [ "Ace" ]

        5 perm. (with repetition) of size 1. Set of 5 items.

SO > v1 2
                #0001 [ "10", "10" ]
                #0002 [ "Joker", "10" ]
                #0003 [ "Queen", "10" ]
                #0004 [ "King", "10" ]
                #0005 [ "Ace", "10" ]
                #0006 [ "10", "Joker" ]
                #0007 [ "Joker", "Joker" ]
                #0008 [ "Queen", "Joker" ]
                #0009 [ "King", "Joker" ]
                #0010 [ "Ace", "Joker" ]
                #0011 [ "10", "Queen" ]
                #0012 [ "Joker", "Queen" ]
                #0013 [ "Queen", "Queen" ]
                #0014 [ "King", "Queen" ]
                #0015 [ "Ace", "Queen" ]
                #0016 [ "10", "King" ]
                #0017 [ "Joker", "King" ]
                #0018 [ "Queen", "King" ]
                #0019 [ "King", "King" ]
                #0020 [ "Ace", "King" ]
                #0021 [ "10", "Ace" ]
                #0022 [ "Joker", "Ace" ]
                #0023 [ "Queen", "Ace" ]
                #0024 [ "King", "Ace" ]
                #0025 [ "Ace", "Ace" ]

        25 perm. (with repetition) of size 2. Set of 5 items.

SO > v1 4
                #0001 [ "10", "10", "10", "10" ]
                #0002 [ "Joker", "10", "10", "10" ]
                #0003 [ "Queen", "10", "10", "10" ]
                #0004 [ "King", "10", "10", "10" ]
                #0005 [ "Ace", "10", "10", "10" ]
//... truncated
                #0624 [ "King", "Ace", "Ace", "Ace" ]
                #0625 [ "Ace", "Ace", "Ace", "Ace" ]

        625 perm. (with repetition) of size 4. Set of 5 items.
        

код

заголовок перм.ч

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    size_t array_size;
    size_t sample_size;

    void** source;
    int (*show_one)(void** source, size_t size);

    size_t  curr_dim;
    size_t* control;
} Perm;

Perm* so_create_perm(
    size_t sample, size_t size, void** source,
    int (*show)(void**, size_t));
Perm* so_destroy_perm(Perm*);
int   so_next_permutation(Perm*, const char* msg);

Вот struct, который абстрагирует процесс. C не имеет указателя self, как Python, поэтому операции получают указатель на экземпляр объекта. source — полиморфный компонент. control — инвертированный массив с индексами.

возможная реализация для perm.c

#include "perm.h"
#include <stdio.h>

Perm* so_create_perm(
    size_t sample, size_t size, void** source,
    int (*show)(void**, size_t))
{
    if (sample == 0) return NULL;
    if (size == 0) return NULL;
    if (sample > size) return NULL;
    Perm * perm = malloc(sizeof(Perm));
    if (perm == NULL) return NULL;
    perm->array_size  = size;
    perm->sample_size = sample;
    perm->curr_dim    = 0;
    perm->source      = source;
    perm->show_one    = show;
    perm->control =
        malloc(perm->sample_size * sizeof(size_t));
    if (perm->control == NULL)
    {
        free(perm);
        fprintf(
            stderr,
            "Error: could not allocate control array\n");
        return NULL;
    }
    for (size_t i = 0; i < perm->sample_size; i += 1)
    {
        perm->control[i] = 0;
    };
    return perm;
};

Perm* so_destroy_perm(Perm* to_go)
{
    if (to_go == NULL) return NULL;
    free(to_go->control);
    free(to_go);
    return NULL;
};

int so_next_permutation(Perm* perm, const char* msg)
{
    if (msg != NULL)
        printf("%s[ ", msg);
    else
        printf("[ ");
    for (size_t i = 0; i < perm->sample_size - 1; i += 1)
    {
        perm->show_one(perm->source, perm->control[i]);
        printf(", ");
    }
    perm->show_one(
        perm->source, perm->control[perm->sample_size - 1]);
    printf(" ]\n");
    // update control indexes
    if (perm->control[0] < perm->array_size - 1)
    {
        perm->control[0] += 1;
        return 1;
    }
    // end of a dimension
    perm->control[0] = 0;
    for (size_t dim = 1; dim < perm->sample_size; dim += 1)
    {
        if (perm->control[dim] < perm->array_size - 1)
        {
            perm->control[dim] += 1;
            return 1;
        };
        perm->control[dim] = 0;
    };
    return 0;
}

пример 1 в v0.c

#include <stdio.h>
#include <stdlib.h>

#include "perm.h"

int show_one(void**, size_t);

int main(int argc, char* argv[])
{
    size_t sample_size = 1;
    if (argc > 1) sample_size = atoi(argv[1]);
    char   my_test[] = {'a', 'b', 'c', 'd'};
    size_t n_items   = sizeof(my_test) / sizeof(my_test[0]);
    Perm*  p         = so_create_perm(
        sample_size, n_items, (void**)my_test, show_one);
    size_t count   = 0;
    char   msg[20] = {0};
    do {
        count += 1;
        sprintf(msg, "\t\t#%04d ", (int)count);
    } while (so_next_permutation(p, msg) != 0);
    p = so_destroy_perm(p);
    fprintf(
        stderr,
        "\n\t%llu perm. (with "
        "repetition) of size %llu. Set of %llu "
        "items. \n",
        count, sample_size, n_items);
    return 0;
};

int show_one(void** source, size_t pos)
{   if (source == NULL) return -1;
    char* p = (char*)source;
    printf("%c", p[pos]);
    return 0;
}

пример 2 в v1.c

#include <stdio.h>
#include <stdlib.h>

#include "perm.h"

int show_one(void**, size_t);

int main(int argc,char** argv)
{
    size_t size = 1;
    if (argc > 1) size = atoi(argv[1]);
    const char* my_test[] = {
        "10", "Joker", "Queen", "King", "Ace"};
    size_t n_items = sizeof(my_test)/sizeof(my_test[0]);
    Perm*        p = so_create_perm(
        size, n_items,
        (void**)my_test, show_one);
    size_t count   = 0;
    char         msg[20] = {0};
    do {
        count += 1;
        sprintf(msg, "\t\t#%04d ", (int)count);
    } while (so_next_permutation(p, msg) != 0);
    p = so_destroy_perm(p);
    fprintf(
        stderr,
        "\n\t%llu perm. (with "
        "repetition) of size %llu. Set of %llu "
        "items. \n",
        count, size, n_items);
    return 0;
};

int show_one(void** source, size_t pos)
{
    if (source == NULL) return -1;
    const char** array = (const char**)source;
    printf("\"%s\"", array[pos]);
    return 0;
}

о next_permutation

Полный код приведен выше, но здесь перестановки рассчитываются в коде next_permutation:

    // update control indexes
    if (perm->control[0] < perm->array_size - 1)
    {
        perm->control[0] += 1;
        return 1;
    }
    // end of a dimension
    perm->control[0] = 0;
    for (size_t dim = 1; dim < perm->sample_size; dim += 1)
    {
        if (perm->control[dim] < perm->array_size - 1)
        {
            perm->control[dim] += 1;
            return 1;
        };
        perm->control[dim] = 0;
    };