Вложенные для циклов - как игнорировать определенные комбинации?

Question

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

У меня есть 7 вложенных циклов внутри друг друга, но мне нужны только комбинации «для переменных», в которых никто не повторяется. Так, например, 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 является дубликатом функция теста, с возвратами верно, если нет дубликатов): не

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]); 
         }} 
        }} 
       }} 
      }} 
     }} 
    }} 
} 

Как я мог сделать это быстрее, есть другое решение, а не для петель может быть?

Спасибо.

Answer 1

Что вы здесь делаете, итерации по всем перестановкам из списка из 14 секретных значений.

В общем, чтобы просмотреть все перестановки списка секретных вещей, вы посещаете каждый элемент списка. Для каждого элемента сформируйте новый список, содержащий все другие элементы оригинального списка. Получите все перестановки , чтобы список, добавьте элемент к каждому, и у вас есть все перестановки исходного списка, которые могут начинаться с этого конкретного элемента. Когда вы выполнили все элементы, все готово.

Поиск всех перестановок списка с одним элементом в нем - простая задача, конечно.

Так что у нас есть что-то вроде этого:

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); 
} 

Что это делает рекурсивно выполнить операцию, которую я описал выше. Функция «pluckElement» возвращает элемент из списка, а - этого списка. Затем функция «переместить» либо выполняет операцию, переданную при полной перестановке исходного списка (когда он замечает, что список остатков пуст), либо вызывает рекурсивно с каждым элементом списка, который он передал.

Чтобы использовать эту функцию, вы бы просто сделать это:

forEachPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], check); 

редактировать — если вы хотите быть выщипывание только определенное количество значений из исходного списка, то выше было бы быть изменен; дай мне секунду.

OK - если вы хотите передать список из 14 элементов, но для функции «вызывается» для каждого отдельного списка (скажем) 7 из 14, вы можете изменить функцию следующим образом. Внешняя функция «forEachPermutation» принимает дополнительный параметр «len», чтобы указать длину требуемой строки. Затем функция «переместить» проверяет, является ли «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 }; 
    } 

    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); 
} 

и вы бы назвали его

forEachPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], 7, check); 

Другой редактировать — если по какой-то причине вы хотите СОХРАНИТЬ перестановок после функции «операции» обрабатывает каждый из них, то мы 'придется учитывать тот факт, что используемый частичный массив перезаписывается. Вызов «операции» может быть изменен:

if (partial.length === len) 
    operation(partial.slice(0)); 

Это делает копию «частичного» массив, так что каждый вызов «операции» получает свой собственный массив для использования. Конечно, это сделает процесс медленнее.

Answer 2

Проблема в том, что вы выполняете дополнительную работу. В вашей петле c вы уже знаете, что a и b не равны, но вы все равно проверяете. Вы можете использовать гибкость с-стилем for петель:

for(var a=0;a<14;a++) { 
    for(var b=0;b<14 && b!=a;b++) { 
     for(var c=0;c<14 && c!=a && c!=b;c++) { 
      ... 
     } 
    } 
} 

Это становится немного подробно внутренним цикл, но, по крайней мере просто.