Все комбинации свойств в массиве

Question

Хорошо, я обманывал эту тему последние пару дней. Что опрятных (все без ОГРОМНЫЙ накладные расходы) способ создания массива всех возможных комбинаций

var input = [ 
    {a: 1}, {a: 2, b: 3}, 
    {b: 4}, {b: 5}, {a: 6} 
]; 

Итак, что я хочу, чтобы генерировать следующий:

var output = [ 
    {a: 1}, {b: 4}, {b: 5}, {a: 6}, 
    {a: 1, b: 4}, {a: 1, b: 5}, 
    {a: 6, b: 4}, {a: 6, b: 5}, 
    {a: 2, b: 3} 
]; 

Дело в том, однако, что в моем конкретный случай. Я говорю о 4 свойствах (и мне действительно нужно создать отдельный массив для каждого набора различных наборов свойств, однако это обе вещи, которые я должен реализовать позже). Однако я ищу только какой-то общий код psuedo о том, как подойти к этой проблеме, а не кому-то, пишущим это для меня или что-то в этом роде.

Я чувствую, что это должно было быть чем-то, что я должен был бы выяснить, но я просто не добираюсь туда. Сначала я генерирую отдельные массивы для всех комбинаций свойств (все a, все b, все c, все ab, все bc, и т. Д.). Однако дело в том, что с 3-мя свойствами вы уже должны добавить для каждого a все b's, c и bc. Теперь написать это для одного свойства достаточно просто, но написать общее решение, которое делает это для n-свойств, просто полностью ускользает от меня.

Answer 1

Я не уверен, что я действительно понимаю требование, но вы можете попробовать рекурсивное решение по этим направлениям (в псевдокоде не Javascript):

def generate(i,C): 
    # C is a dictionary representing the currently defined properties 
    # We are allowed to add to our set of properties from the choices input[i],input[i+1],... 

    # First choose a non-conflicting set of additional properties to add 
    while i<len(input): 
     if all of properties in input[i] are not in C: 
      Add properties in input[i] to C 
      solutions.append(C) 
      generate(i+1,C) 
      Remove properties in input[i] from C 
     i++ 

generate(0,{})