Using recursion to finds number of combinations of selecting 5 cards from 52 cards, 3819816 combinations found instead of 2598960

huangapple go评论62阅读模式
英文:

Using recursion to finds number of combinations of selecting 5 cards from 52 cards, 3819816 combinations found instead of 2598960

问题

以下是代码部分的翻译:

const cards = [];
for (let i = 0; i < 52; i++) {
  cards.push(i);
}
const s = new Set();
const recursion = function (arr, n) {
  if (arr.length < 5) {
    for (let i = n; i < cards.length; i++) {
      recursion(arr.concat([cards[i]]), i);
    }
  } else {
    s.add(arr.join(","));
  }
};
recursion([], 0);
document.write(s.size);

这段代码的目标是从52张卡牌中选择5张卡牌的所有组合,但实际输出结果为3819816,而期望结果应该是2598960。出现这个问题可能是由于递归算法的实现中有一些错误。

英文:

I was trying to use recursion to list all combinations of selecting 5 cards from 52 cards:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const cards=[];
for(let i=0;i&lt;52;i++){
  cards.push(i);
}
const s=new Set();
const recursion=function(arr,n){
  if(arr.length&lt;5){
    for(let i=n;i&lt;cards.length;i++){
      recursion(arr.concat([cards[i]]),i);
    }
  }else{
    s.add(arr.join(&quot;,&quot;));
  }
};
recursion([],0);
document.write(s.size);

<!-- end snippet -->

The expected count should be 2598960, but the output now is 3819816, whats wrong with the code?

答案1

得分: 1

代码输出为3819816而不是2598960的原因是内部循环中的条件未检查数组的总长度,而只检查当前迭代的长度。

英文:

The reason why the code is producing an output of 3819816 instead of 2598960 is that the condition in the inner loop is not checking for the total length of the array, but only for the length of the current iteration.

答案2

得分: 0

通过将卡片数量减少到5张并检查结果,您可以看到“current”卡片被多次包含,即:

const cards = [];
for (let i = 0; i < 5; i++) {
  cards.push(i);
}
console.log(cards.length)
const s = new Set();
const recursion = function(arr, n) {
  if (arr.length < 5) {
    for (let i = n; i < cards.length; i++) {
      recursion(arr.concat([cards[i]]), i);
    }
  } else {
    s.add(arr.join(","));
    console.log(s.size, arr.join(","))
  }
};
recursion([], 0);
console.log(s.size);

要移除“current”卡片,您可以在下一个递归中添加1:

recursion(arr.concat([cards[i]]), i+1);

这将为5张卡片提供期望的结果:1种组合

'0,0,0,0,0'
'0,0,0,0,1'
'0,0,0,0,2'
等等

然后,当应用到52张卡片时,将得到期望的结果:

const cards = [];
for (let i = 0; i < 52; i++) {
  cards.push(i);
}
console.log(cards.length)
const s = a Set();
const recursion = function(arr, n) {
  if (arr.length < 5) {
    for (let i = n; i < cards.length; i++) {
      recursion(arr.concat([cards[i]]), i+1);
    }
  } else {
    s.add(arr.join(","));
    //console.log(s.size, arr.join(",")) 
  }
};
recursion([], 0);
console.log(s.size);
英文:

By reducing the number of cards to 5, and examining the results, you can see that the "current" card is included multiple times, ie:

<!-- begin snippet: js hide: true console: true babel: false -->

<!-- language: lang-js -->

const cards = [];
for (let i = 0; i &lt; 5; i++) {
  cards.push(i);
}
console.log(cards.length)
const s = new Set();
const recursion = function(arr, n) {
  if (arr.length &lt; 5) {
    for (let i = n; i &lt; cards.length; i++) {
      recursion(arr.concat([cards[i]]), i);
    }
  } else {
    s.add(arr.join(&quot;,&quot;));
    console.log(s.size, arr.join(&quot;,&quot;))
  }
};
recursion([], 0);
console.log(s.size);

<!-- end snippet -->

 &#39;0,0,0,0,0&#39;
 &#39;0,0,0,0,1&#39;
 &#39;0,0,0,0,2&#39;
 etc

To remove the "current" card you can add 1 to the next recursion:

    recursion(arr.concat([cards[i]]), i+1);

giving, for 5 cards, the expected result: 1 combination

<!-- begin snippet: js hide: true console: true babel: false -->

<!-- language: lang-js -->

const cards = [];
for (let i = 0; i &lt; 5; i++) {
  cards.push(i);
}
console.log(cards.length)
const s = new Set();
const recursion = function(arr, n) {
  if (arr.length &lt; 5) {
    for (let i = n; i &lt; cards.length; i++) {
      recursion(arr.concat([cards[i]]), i+1);
    }
  } else {
    s.add(arr.join(&quot;,&quot;));
    console.log(s.size, arr.join(&quot;,&quot;)) 
  }
};
recursion([], 0);
console.log(s.size);

<!-- end snippet -->

Then when applied to 52 cards, gives the expected result:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const cards = [];
for (let i = 0; i &lt; 52; i++) {
  cards.push(i);
}
console.log(cards.length)
const s = new Set();
const recursion = function(arr, n) {
  if (arr.length &lt; 5) {
    for (let i = n; i &lt; cards.length; i++) {
      recursion(arr.concat([cards[i]]), i+1);
    }
  } else {
    s.add(arr.join(&quot;,&quot;));
    //console.log(s.size, arr.join(&quot;,&quot;)) 
  }
};
recursion([], 0);
console.log(s.size);

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年3月1日 15:42:44
  • 转载请务必保留本文链接:https://go.coder-hub.com/75600770.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定