Перестановка массива символов В С

Question

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

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

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

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

Мой начальный массив выглядит следующим образом

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

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

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

Итак

«Привет»

.

.

.

"Школьный автобусШкольный автобусШкольный автобусШкольный автобус"

Answer 1

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

#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 будет иметь:

p = [3, 2, 1, 0]

Берегите себя, 0 - 1-е, 1 - 2-е и т. д.

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

PD1: этот код реализует правильное определение перестановки (R-перестановка - это биекция. Кардиналмножество всех биений от N_n до N_n точно равно n!)

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

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

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

Если это так, подумайте о своем выводе в четырех случаях: для вывода, сгенерированного из одного, двух, трех или четырех элементов.Для вывода, сгенерированного из 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 числом вложенных циклов.Имейте в виду, что количество циклов увеличивается экспоненциально с увеличением количества элементов ввода, поэтому это может быть довольно быстро.

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

Обновление: Вот рекурсивная функция псевдокода, которая может генерировать эти псевдоперестановки:

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.Надеемся, что входная размерность не будет такой большой, что это будет слишком глубоко для вашего процессора.