Перестановка массива char В C

Question

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

Массив символов - это массив **, который я повторяю на основе числа, введенного пользователем, и затем меняю пространство для каждого слова (по 40 символов). Номер, введенный пользователем, - это длина массива, и это номер, который они ожидают ввести. Эта часть работает так, как ожидалось.

У меня возникают проблемы с итерацией через массив символов и вычислением перестановки всего набора (** массива). Затем я хочу иметь еще один массив символов, состоящий из всех перестановок набора. Теперь просто перестановки единичных индексов в ** массиве, а не отдельные символы отдельных индексов.

Есть ли у кого-нибудь советы о том, как успешно это сделать, независимо от размера исходного набора? Я предполагаю, что было бы намного проще, если бы размер набора был статическим.

Мой исходный массив выглядит это как пример

char *array[] = { 
    "Hello", 
    "Calculator", 
    "Pencil", 
    "School Bus" 
}; 

Который будет проходить в ** массиве, с «Hello» в массиве [0] и «Школьный автобус» в массиве [3], с '\ 0' в конце каждого.

Я хочу перестановку быть на индексов, а не символов.

Так

"Здравствуйте"

.

.

.

«Школа BusSchool BusSchool BusSchool автобус»

Answer 1

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

Если да, подумайте о своем выходе в четырех случаях: для вывода, генерируемого одним, двумя, тремя или четырьмя элементами. Для вывода, генерируемого из n элементов, у вас есть n^n возможностей. Для всех четырех из этих случаев это дает вам 1^1 + 2^2 + 3^3 + 4^4 = 288 возможных выходов.

Ваш выход перестановок 1-элемент просто: 0, 1, 2, 3

Ваш 2-элемент вывода перестановок могут быть получены с помощью псевдокода:

for i = 0 to 3 { 
    for j = 0 to 3 { 
     next_permutation = {i, j} 
    } 
} 

Для 3- и 4-элементный вывод, перестановки могут быть сгенерированы с использованием трех и четырех вложенных циклов соответственно. Для некоторого произвольного количества элементов ввода x вы можете сгенерировать перестановки с использованием той же методики с числом вложенных циклов x. Будьте предупреждены, что число циклов требует экспоненциального роста с количеством входных элементов, поэтому это может стать довольно уродливым.

Вы можете использовать числа из этих перестановок в качестве индексов в свой начальный массив, чтобы генерировать выходные данные как строки (как в вашем примере).

Update: Вот рекурсивный псевдокод функция, которая может генерировать эти псевдо-перестановки:

int output_array[dimension] = {0}; 
generate_combinations (unsigned dimension, int index) { 
    for i = 0 to (dimension-1) { 
     output_array[index] = i; 
     if index == 0 
      next_permutation = output_array 
     else 
      generate_combinations(dimension, index-1) 
     endif 
    } 
} 

Вы могли бы использовать это с dimension набором к количеству элементов в вашем входном массиве и index = dimension - 1. Надеемся, что размер входных данных не будет настолько большим, что это слишком сильно усложнит работу процессора.

Answer 2

Вот глупый генератор перестановок (до N = 32 ... или 64).

#include <stdio.h> 

const int N = 5; 
int x[N]; 

int main(void) { 

    int i,j; 

    x[0]=-1; 
    unsigned mask = -1; // unused numbers 

    for(i=0;;) { 
    for(j=x[i]+1; j<N; j++) { // check remaining numbers 
     if((mask>>j)&1) { // bit j is 1 -> not used yet 
     x[i] = j; // store the number 
     mask ^= (1<<x[i]); // mask used 
     // try going further, or print the permutation 
     if(++i>=N) { for(j=0; j<N; j++) printf("%3i", x[j]); printf("\n"); } 
      else x[i]=-1; // start next cell from 0 
     break; 
     } 
    } 
    // go back if there's no more numbers or cells 
    if((j>=N) || (i>=N)) { 
     if(--i<0) break; 
     mask ^= (1<<x[i]); 
    } 
    } 

} 

Answer 3

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

void CalculatePermutations(unsigned long permSize, const char** candidates, const char** currentPerm, unsigned long currentPermIdx, const char** ouputBuffer, unsigned long* nextOutputIdx) 
{ 
    //base case (found a single permutation) 
    if(currentPermIdx >= permSize){ 
     unsigned long i = 0; 
     for(i = 0; i < permSize; ++i){ 
      ouputBuffer[*nextOutputIdx] = currentPerm[i]; 
      (*nextOutputIdx)++; 
     } 
     return; 
    } 

    //recursive case 
    unsigned long i = 0; 
    for(i = 0; i < permSize; ++i){ 
     if(candidates[i]){ 
      currentPerm[currentPermIdx] = candidates[i]; //choose this candidate 
      candidates[i] = NULL; //mark as no longer a candidate 
      CalculatePermutations(permSize, candidates, currentPerm, currentPermIdx + 1, ouputBuffer, nextOutputIdx); 
      candidates[i] = currentPerm[currentPermIdx]; //restore this as a possible candidate 
     } 
    } 
} 

int main(int argc, char** argv) 
{ 
    const char* allStrings[8] = {"0", "1", "2", "3", "4", "5", "6", "7"}; 
    static const char* allPermutations[322560]; // = fact(8) * 8 
    const char* permBuffer[8]; 
    unsigned long nextOutputIdx = 0; 

    CalculatePermutations(8, allStrings, permBuffer, 0, allPermutations, &nextOutputIdx); 

    for(unsigned long i = 0; i < 322560; ++i){ 
     printf("%s", allPermutations[i]); 
     if(i % 8 == 7){ 
      printf("\n"); 
     } else { 
      printf(", "); 
     } 
    } 

    return 0; 
} 

Answer 4

здесь мой код, который дает нам r-перестановку n! возможные перестановки. Код работает со всеми видами размера (я только проверить с 3 !, 4 !, 5 и 8, и всегда работает правильно, поэтому я suppouse, что работает сразу!):

#include <stdio.h> 
#include <stdint.h> 


enum { NPER = 4, }; 

static const char *DukeQuote[NPER] = { 
    "Shake it, baby!", 
    "You wanna dance?", 
    "Suck it down!", 
    "Let's rock!", 
}; 

void fill(const uint32_t, uint32_t * const); 
void fact(const uint32_t, uint32_t * const); 
void perm(uint32_t, const uint32_t, const uint32_t * const, uint32_t * const); 


int main(void) 
{ 
    uint32_t f[NPER+1]; 
    uint32_t p[NPER]; 
    uint32_t r, s; 

    /* Generate look-up table for NPER! factorial */ 
    fact(NPER, f); 

    /* Show all string permutations */ 
    for(r = 0; r < f[NPER]; r++) 
    { 
    perm(r, NPER, f, p); 

    for(s = 0; s < NPER; s++) 
     printf("%s, ", DukeQuote[p[s]]); 
    printf("\n"); 
    } 

    return 0; 
} 

/* Generate look-up table for n! factorial. 
That's a trick to improve execution */ 
void fact(const uint32_t n, uint32_t * const f) 
{ 
    uint32_t k; 

    for(f[0] = 1, k = 1; k <= n; k++) 
    f[k] = f[k-1] * k; 
} 

/* Fill the vector starting to 0 up to n-1 */ 
void fill(const uint32_t n, uint32_t * const p) 
{ 
    uint32_t i; 

    for(i = 0; i < n; i++) 
    p[i] = i; 
} 

/* Give us the r-permutation of n! possible permutations. 
r-permutation will be inside p vector */ 
void perm(uint32_t r, const uint32_t n, const uint32_t * const f, uint32_t * const p) 
{ 
    uint32_t i, j; 

    fill(n, p); 

    for(i = n-1; i > 0; i--) 
    { 
    uint32_t s; 

    j = r/f[i]; 
    r %= f[i]; 
    s = p[j]; 

    for(; j < i; j++) 
     p[j] = p[j+1]; 
    p[i] = s; 
    } 

} 

Например, если вы хотите первая перестановка 4! Тогда: с-плюс

perm(0, 4, f, p) 

где р будет иметь:

p = [3, 2, 1, 0] 

Позаботьтесь, 0 1th, 1 является 2th, и так далее.

Вы можете использовать p [i] как индексы в вашем массиве строк, как я использовал в массиве DukeQuote.

PD1: Этот код реализует правильное определение перестановки (А г-перестановка биекция Кардинальное множества всех биекций N_n к ñ_ñ является именно п.!)

PD2: Я надеюсь, что мой ошибки в моем бедном английском не влияют на цель моего объяснения.