Как выполнить проверку всех возможных вариантов?

Question

[Алексей]

Добрый день,

Есть столбцы, которые могут расшириться, но думаю не более пяти.
Строки будут увеличиваться постоянно.
Значения будут всегда разными.

Например:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

Каждую строку надо сравнить с результатом (обозначим: "счёт"), но по особому.

Хочу, чтобы программа учла все возможные варианты.
Например сначала сравнить каждый столбец с "счёт",
потом столбы 1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 1 9, 1 10 с "счёт"
2 1, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 2 9, 2 10 с "счёт"
...
1 2 3, 1 2 4, 1 2 5, 1 2 6, 1 2 7, 1 2 8, 1 2 9, 1 2 10 с "счёт"
1 3 2, 1 3 4, 1 3 5, 1 3 6, 1 3 7, 1 3 8, 1 3 9, 1 3 10 с "счёт"
и так вплоть до
1 2 3 4 5 6 7 8 9 10 с "счёт"

Каждый возможный вариант, я потом должен сохранить результат сравнения, Например (истина/ложь)

Далее результат всех возможных вариантов каждой строки, хочу сравнить и выловить самый лучший вариант, подходящий к результату "счёт"
Дабы потом к этим столбцам поставить одно самое эффективное условие)

Так вот, суть вопроса, посоветуйте, как мне в автоматическом режиме проверить все возможные комбинации проверки?
(в ручную делать с помощью множества конструкций if ((1) && (2) && (3) === счёт) все возможные варианты, крайне не благодарное дело. Не могу придумать алгоритм, как лучше использовать циклы((
По любому есть более простой элегантный способ проверки с менее объемом строк кода, но не придумаю как)

Comments

[Сергей Соколов]

что-то мутно.

1. «Значения будут всегда разными.» и идут две идентичные строки.
   
2. «лучший вариант, подходящий к результату "счёт"» – как он должен «подходить», что является мерой подходящности? )
   
3. if ((1) && (2) && (3) === счёт) счёт имеет тип Boolean?
   

Попробуйте упростить ваш вопрос до изолированного примера кода.

[Алексей]

Сергей Соколов, Сергей Соколов, Я всё-таки пока сам не могу сформулировать правильно, что мне именно нужно)

Пока надумал так:

Шаг №1

"Нужно найти все возможные комбинации и сохранить их в массив"
Например 2 столбца. Каждый столбец имеет переменную с данными "1"
a = 1; b = 1; c = 1;

происходит парсинг всех возможных комбинаций, все они должны сохранится в массив для дальнейшего сравнения)

комбо 1: a arr[0] = [a]
комбо 2: b arr[1] = [b]
комбо 3: c arr[2] = [c]
комбо 4: a b arr[3] = [a, b]
комбо 5: a c arr[4] = [a, c]
комбо 6: b c arr[5] = [b, c]
комбо 7: a b c arr[6] = [a, b, c]

Из экселя я беру данные из определенных столбцов - сохраняю в переменные и сравниваю их с массивом из шаг №1

Например:
Входные данные также будут 1 или 0.

строка №1 из экселя: var1 = 1, var2 = 0, var3 = 1;
строка №2 из экселя: var1 = 0, var2 = 0, var3 = 1;

Дальше пока что смутно представляю реализацию...
как-то надо сопоставить "var1" с "b" и "var2" с "a" и "var3" c "c"
Далее,

Первый проход:
если "а" есть в массиве в текущем прохождении цикла, начать сравнивать её только с var2 каждой строки
если "а" и "b" есть в массиве в текущем прохождении цикла, начать сравнивать её только с var2 и c var1 каждой строки

выглядеть примерно должно так:

excel парсер с циклом "i" массив комбинаций с циклом "j"
строка 1: var1 = 1, var2 = 0, var3 = 1; a if (var2 === a) { counter[j][переменная1]++
} else if var2 !== a { counter[j][переменная2]++ }
b
c
a b if ((var2 === a) && (var1 === b)) { counter[j][переменная1]++
} else if ((var2 !== a) || (var1 !== b)) { counter[j][переменная2]++ }
a c
b c
a b c
строка 2: var1, var2, var3 a
b
c
a b
a c
b c
a b c
...



Потом я буду смотреть лучший результат между всеми переменными в counter[] и выберу несколько лучших комбинаций для использования в своих целях)

[Сергей Соколов]

Evelate, у вас тут какая-то нечетко сформулированная задача. Но для «шага номер 1» я вам предложил вроде бы неплохой вариант – когда нужно все возможные комбинации собрать из N элементов, подойдёт перебор двоичной записи чисел от 1 до 2^N. В «комбо» входят те элементы, напротив которых включена единичка в записи числа:

X   a  b  c  arr[]
1   0  0  1  c
2   0  1  0  b
3   0  1  1  b, c
4   1  0  0  a
5   1  0  1  a, c
6   1  1  0  a, b
7   1  1  1  a, b, c

[Алексей]

for( i = 1; i < n; i++) {
        sum = 0;
        for( bit = 0; bit < len; bit++) {
            if( i & (1 << bit)) {
                console.log(i & (1 << bit));
                result.push(arr[bit]);
            }
        }
}

Туго что-то мне даётся понимание работы данного кода)
Сейчас данный цикл просто записывает подряд все возможные комбинации. Что-то не соображу как сделать, чтобы они разбивались на под массивы?)
arr[0] [a]
arr[1] [b]
arr[2] [c]
arr[3] [a, b]
arr[4] [a, c]
arr[5] [b, c]
arr[6] [a, b, c]

Answer 1

[Сергей Соколов]

Кажется, вам подойдёт такой простой алгоритм: перебрать все числа в двоичной записи от 1 до 2ⁿ, и брать те элементы строки, которым соответствует 1.

Набросал функцию, подбирающую из данных элементов комбинацию, дающую наиболее близкую сумму к заданной:

function nearest(arr, total) {
  var len = arr.length
    , i
    , bit
    , sum
    , n = Math.pow(2, len)
    , currDist
    , index = undefined
    , dist = undefined
    , result = []
  ;
  
  for( i = 1; i < n; i++) {
    sum = 0;
    for( bit = 0; bit < len; bit++) {
      if( i & (1 << bit)) sum += arr[bit];
    }
    
    currDist = Math.abs(total - sum);
    if( typeof dist === 'undefined' || dist > currDist) {
      index = i;
      dist = currDist;
      if( dist === 0) break;
    }
  }
  
  for(bit = 0; bit < len; bit++) {
    if( index & (1 << bit)) result.push(arr[bit]);
  }
  
  return result;  
}

nearest([1,3,4,6,8], 12) // [1,3,8]
nearest([1,2,4,6,8], 12) // [2,4,6]
nearest([7,9,13,19,28], 12) // [13] dist = 1
nearest([7,9,13,19,28], 28) // [9,19] не [28] т.к. останавливается на первом найденном варианте