嵌套for循环 - 如何忽略某些组合？ [英] Nested for loops - how to ignore certain combinations?
问题描述
我正在做某种暴力攻击来解决问题。理论上它是一个有效的解决方案，它确实是，但它需要相当长的时间。
我有7个嵌套for循环，但我只需要组合'for variables'，其中没有重复。所以例如允许使用1,2,3,4,5,6,7，但应忽略1,1,3,4,5,6,7。我目前正在使用函数来检查数组中的重复项：
http://www.groggyjava.tv/freebies/duplicates.html
但是我觉得我会更好如果我可以立即忽略这些组合，而不是反复使用每个单个组合的那个功能。现在我正在评估14 ^ 7 = 105.413.504组合，但只需要14 nPr 7 = 17.297.280。
我的代码目前是（其中） hgd是重复的测试函数，如果没有重复，则返回true）：
for（var a = 0; a< 14; a ++）{
for（var b = 0; b< 14; b ++）{if（hgd（[a，b]））{
for（var c = 0; c< 14; c ++） {if（hgd（[a，b，c]））{
for（var d = 0; d< 14; d ++）{if（hgd（[a，b，c，d]））{
for（var e = 0; e< 14; e ++）{if（hgd（[a，b，c，d，e]））{
for（var f = 0; f< 14; f ++）{if（hgd（[a，b，c，d，e，f]））{
for（var g = 0; g< 14; g ++）{if（hgd（[a，b， c，d，e，f，g]））{
check（[a，b，c，d，e，f，g]）;
}}
}}
}}
}}
}}
}}
}
我怎样才能让它更快，是否有其他解决方案而不是for循环呢？
谢谢。
你在这里做的是迭代所有的排列 14个谨慎值的列表。
通常，要访问谨慎事物列表的所有排列，您可以访问列表中的每个元素。对于每个元素，形成一个包含原始列表的所有其他元素的新列表。获取 列表的所有排列，将元素添加到每个列表中，并且您已获得可以从该特定元素开始的原始列表的所有排列。当你完成所有元素后，你就完成了。
当然，查找包含一个元素的列表的所有排列是一项简单的任务。 p>
因此我们得到的是这样的：
function forEachPermutation （list，operation）{
function pluckElement（list，index）{
var e = list [index];
var l = [];
for（var i = 0; i< list.length; ++ i）
if（i！== index）l.push（list [i]）;
return {element：e，remainder：l};
}
函数permute（部分，余数）{
if（remainder.length === 0）
operation（partial）;
else {
for（var i = 0; i< remainder.length; ++ i）{
var plucked = pluckElement（remainder，i）;
partial.push（plucked.element）;
permute（partial，plucked.remainder）;
partial.length--;
}
}
}
permute（[]，list）;
}
这样做是递归地执行我上面描述的操作。 pluckElement函数返回列表中的元素以及该列表的 rest 。然后，permute函数执行在原始列表的完整排列中传入的操作（当它注意到剩余列表为空时），或者以传递的列表的每个元素递归地调用自身。
要使用该功能，您只需执行以下操作：
forEachPermutation（ [0,1,2,3,4,5,6,7,8,9,10,11,12,13]，检查）;
edit —如果你想从原始列表中仅提取一定数量的值，则必须修改上述值;给我一个时间。
好的 - 如果你想传入（比方说）14个元素的列表，但是为每个不同的列表调用了operation函数（比如）14中的7个，您可以按如下方式修改功能。外部forEachPermutation函数将采用额外的len参数，以告诉它所需字符串的长度。然后，permute函数将检查partial.length是否是该目标长度，而不是检查空余数。
function forEachPermutation（list，len，operation）{
function pluckElement（list，index）{
var e = list [index];
var l = [];
for（var i = 0; i< list.length; ++ i）
if（i！== index）l.push（list [i]）;
return {element：e，remainder：l};
}
函数permute（部分，余数）{
if（partial.length === len）
operation（partial）;
else {
for（var i = 0; i< remainder.length; ++ i）{
var plucked = pluckElement（remainder，i）;
partial.push（plucked.element）;
permute（partial，plucked.remainder）;
partial.length--;
}
}
}
permute（[]，list）;
}
你打电话给
forEachPermutation（[0,1,2,3,4,5,6,7,8,9,10,11,12,13]，7，检查）;
另一个编辑—如果出于某种原因你希望在操作函数处理每一个之后保存排列，那么我们必须考虑到正在使用的部分数组被覆盖的事实。可以更改对操作的调用：
if（partial.length === len）
操作（ partial.slice（0））;
这是部分数组的副本，因此每次操作调用都会得到它非常自己的数组使用。当然，它会让这个过程变慢。
I'm doing some kind of brute force attack to solve a problem. Theoratically it is a working solution, it also really is, but it takes rather long.
I have 7 nested for loops within each other, but I only need the combinations of the 'for variables' in which none are repeated. So e.g. 1,2,3,4,5,6,7 is allowed, but 1,1,3,4,5,6,7 should be ignored. I'm currently using a function to check for duplicate items in an array:
http://www.groggyjava.tv/freebies/duplicates.html
However I think I'd be better off if I could immediately ignore those combinations instead of using that function over and over for every single combination. Now I'm evaluating 14^7 = 105.413.504 combinations, but only 14 nPr 7 = 17.297.280 of them are necessary.
My code currently is (in which hgd is the duplicate test function, with returns true if no duplicates):
for(var a=0;a<14;a++) {
for(var b=0;b<14;b++) {if(hgd([a,b])) {
for(var c=0;c<14;c++) {if(hgd([a,b,c])) {
for(var d=0;d<14;d++) {if(hgd([a,b,c,d])) {
for(var e=0;e<14;e++) {if(hgd([a,b,c,d,e])) {
for(var f=0;f<14;f++) {if(hgd([a,b,c,d,e,f])) {
for(var g=0;g<14;g++) {if(hgd([a,b,c,d,e,f,g])) {
check([a,b,c,d,e,f,g]);
}}
}}
}}
}}
}}
}}
}
How could I make this faster, is there another solution instead of for loops perhaps?
Thanks.
What you're doing here is iterating over all the permutations of a list of 14 discreet values.
In general, to visit all the permutations of a list of discreet things, you visit each element of the list. For each element, form a new list containing all other elements of the original list. Get all the permutations of that list, prepend the element to each, and you've got all the permutations of the original list that can start with that particular element. When you've done all the elements, you're done.
Finding all permutations of a list with one element in it is a simple task, of course.
Thus what we've got is something like this:
function forEachPermutation(list, operation) {
function pluckElement(list, index) {
var e = list[index];
var l = [];
for (var i = 0; i < list.length; ++i)
if (i !== index) l.push(list[i]);
return { element: e, remainder: l };
}
function permute(partial, remainder) {
if (remainder.length === 0)
operation(partial);
else {
for (var i = 0; i < remainder.length; ++i) {
var plucked = pluckElement(remainder, i);
partial.push(plucked.element);
permute(partial, plucked.remainder);
partial.length--;
}
}
}
permute([], list);
}
What that does is recursively carry out the operation I described above. The "pluckElement" function returns an element from a list, and the rest of that list. The "permute" function then either carries out the operation passed in on a complete permutation of the original list (when it notices that the remainder list is empty), or else calls itself recursively with each element of the list it's passed.
To use that function, you'd just do this:
forEachPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], check);
edit — if you want to be plucking only a certain number of values from the original list, then the above would have to be modified; give me a sec.
OK - if you want to pass in a list of (say) 14 elements, but have the "operation" function invoked for each distinct list of (say) 7 of the 14, you could modify the function as follows. The outer "forEachPermutation" function would take an additional "len" parameter, to tell it the length of string desired. Then, the "permute" function would check to see if "partial.length" is that target length, instead of checking for an empty remainder.
function forEachPermutation(list, len, operation) {
function pluckElement(list, index) {
var e = list[index];
var l = [];
for (var i = 0; i < list.length; ++i)
if (i !== index) l.push(list[i]);
return { element: e, remainder: l };
}
function permute(partial, remainder) {
if (partial.length === len)
operation(partial);
else {
for (var i = 0; i < remainder.length; ++i) {
var plucked = pluckElement(remainder, i);
partial.push(plucked.element);
permute(partial, plucked.remainder);
partial.length--;
}
}
}
permute([], list);
}
and you'd call it with
forEachPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], 7, check);
Another edit — if for some reason you want to save the permutations after the "operation" function processes each one, then we'll have to account for the fact that the partial array being used gets overwritten. The call to "operation" can be changed:
if (partial.length === len)
operation(partial.slice(0));
That makes a copy of the "partial" array, so that each invocation of "operation" gets its very own array to use. It'll make the process slower, of course.
这篇关于嵌套for循环 - 如何忽略某些组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
