факториальный массив для крестиков

Question

В настоящее время я пытаюсь научить себя C ++ и программированию в целом.Поэтому, как проект для начинающих, я создаю генетический алгоритм, который создает оптимальный ИИ для игры в крестики-нолики.Я не зачислен ни в какие классы программирования, так что это не домашняя работа.Я просто очень заинтересован в искусственном интеллекте.

Итак, я пытаюсь создать многомерный массив факториала, в моем случае 9!,Например, если вы сделали один из 3!это будет массив [3] [6] = {{1, 2, 3}, {1, 3, 2}, {2, 3, 1}, {2, 1, 3}, {3, 2, 1}, {3, 1, 2}}.В основном 3!или 3 * 2 * 1 - это количество способов упорядочить 3 числа по порядку.

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

Так что, если вы знаете, как ее решить, это здорово.Если вы можете дать формат кодирования, это лучше.Любая помощь приветствуется.

Также я кодирую это на C ++.

Answer 1

Вы можете использовать функцию next_permutation из STL

http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 2

Я действительно однажды написал алгоритм для этого вручную.Вот оно:

bool incr(int z[NUM_INDICES]){
    int a=NUM_INDICES-1;
    for(int i=NUM_INDICES-2;i>=0;i--)
      if(z[i]>z[i+1]) a--;
      else break;
    if(a==0) return false;
    int b=2147483647,c;
    for(int i=a;i<=NUM_INDICES-1;i++)
      if(z[i]>z[a-1]&&z[i]-z[a-1]<b){
        b=z[i]-z[a-1];
        c=i;
      }
    int temp=z[a-1]; z[a-1]=z[c]; z[c]=temp;
    qsort(z+a,NUM_INDICES-a,sizeof(int),comp);
    return true;
}

Это функция приращения (т. Е. У вас есть массив типа [3,2,4,1], вы передаете его этому, и он изменяет его на [3,4, 1,2]).Он работает на том факте, что если последние d элементы массива расположены в порядке убывания, то следующий массив (в «алфавитном» порядке) должен удовлетворять следующим условиям: 1) последний d+ 1 элементы являются перестановкой между собой;2) элемент d + 1 от последнего к последнему является следующим наивысшим элементом в последних элементах d + 1 ;3) последние элементы d должны быть в порядке возрастания.Вы можете видеть это интуитивно, когда у вас есть что-то вроде [2,5,3, 8,7,6,4,1]: d = 5 в этом случае;3 превращается в следующий наивысший из последних d + 1 = 6 элементов;а последние d = 5 располагаются в порядке возрастания, поэтому становится [2,5,4, 1,3,6,7,8].

Первый цикл в основном определяет* 1 022 * д .Он перебирает массив в обратном порядке, сравнивая последовательные элементы, чтобы определить количество элементов в конце в порядке убывания.В конце цикла a становится первым элементом в последовательности по убыванию.Если a==0, то весь массив находится в порядке убывания, и больше ничего нельзя сделать.

Следующий цикл определяет, каким должен быть элемент d + 1 -го-последнего.Мы указали, что это должен быть следующий самый высокий элемент в последних d + 1 элементах, поэтому этот цикл определяет, что это такое.(Обратите внимание, что z [a-1] - это элемент d + 1 от последнего до последнего.) К концу этого цикла b содержит наименьшее положительное значение z[i]-z[a-1];то есть z[i] должно быть больше, чем z[a-1], но как можно ниже (так, чтобы z[a-1] стал следующим самым высоким элементом).c содержит индекс соответствующего элемента.Мы отбрасываем b, потому что нам нужен только индекс.

Следующие три строки меняются местами z[a-1] и z[c], так что элемент d + 1 -последнийполучает следующий элемент в строке, а другой элемент (z[c]) сохраняет z[a-1].Наконец, мы сортируем последние элементы d , используя qsort (comp должно быть объявлено в другом месте; см. Документацию C ++ по qsort).

Answer 3

Если вам нужна созданная вручную функция для генерации всех перестановок, вы можете использовать

#include <cstdio>
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define GI ({int t;scanf("%d",&t);t;})

int a[22], n;

void swap(int & a, int & b) {
    int t = a; a = b; b = t;
}

void perm(int pos) {
    if(pos==n) {
        REP(i,n) printf("%d ",a[i]); printf("\n");
        return;
    }
    FOR(i,pos,n) {
        swap(a[i],a[pos]);
        perm(pos+1);
        swap(a[pos],a[i]);
    }
    return;
}

int main (int argc, char const* argv[]) {

    n = GI;
    REP(i,n) a[i] = GI;
    perm(0);

    return 0;
}