tic tac toe的阶乘数组
我目前正在尝试自学C++和一般编程。因此，作为一个初学者项目，我正在制作一个遗传算法，它为Tic-Tac-Toe游戏创建了一个最优的人工智能。我没有参加任何编程课程，所以这不是家庭作业。我只是对人工智能很感兴趣。
所以我尝试创建一个阶乘的多维数组，在我的例子中是9！例如，如果你做了3个中的一个！它将是array3 ={ {1，2，3}，{1，3，2}，{2，3，1}，{2，1，3}，{3，2，1}，{3，1，2}}。基本上是3！或者3*2*1是您可以按顺序排列3个数字的数量。
我认为解决方案应该是简单的，但我却卡住了，试图找出一个简单的解决方案。我试着交换它们，试着将它们向右移动，递增等等。有效的方法是显而易见的，我不知道如何对它们进行编码。
所以，如果你知道如何解决这个问题，那就太好了。如果你能给出一个编码格式，那就更好了。任何帮助都是非常感谢的。
另外，我用c++编写了这个代码。
回答 3
Stack Overflow用户
发布于 2012-03-09 12:10:50
你可以使用STL的next_permutation函数
http://www.cplusplus.com/reference/algorithm/next_permutation/
Stack Overflow用户
发布于 2012-03-09 13:06:04
实际上，我曾经手工写过一个算法。这就是它：
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。
第一个循环基本上确定d。它向后循环数组，比较连续的元素，以确定末尾按降序排列的元素的数量。在循环结束时，a成为降序序列中的第一个元素。如果为a==0，则整个数组按降序排列，不能再执行其他操作。
下一个循环确定倒数第d+1个元素应该是什么。我们指定它应该是最后一个d+1元素中的下一个最高元素，所以这个循环决定了它是什么。(请注意，za-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]。最后，我们使用qsort对最后d个元素进行排序(comp必须在其他地方声明；请参阅qsort上的C++文档)。
Stack Overflow用户
发布于 2012-03-09 18:45:10
如果您需要一个手工创建的函数来生成所有排列，您可以使用
#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;
}https://stackoverflow.com/questions/9628782
复制相似问题
腾讯云开发者
