Найти номера, которые являются надмножеством другого номера в списке

Question

Число A является надмножеством числа B, если все биты, установленные на B, также установлены на A. Или A & B == B.

Учитывая список чисел, как я могу определить все числа, которые являются надмножеством любого другого числа в указанном списке?

Простой подход:

for a in list:
  for b in list:
    if a != b and a & b == b:
      print(a + ' is a superset')  

Но этот подход O(n²). Есть ли какое-нибудь более эффективное решение?

Неважно, какие подмножества, нужна только информация о надмножествах, и список может быть отсортирован.

Answer 1

Вот некоторые улучшения, если список отсортирован:

var getSupersetList = function(sortedList){
  var supersetList = [];

  //You don't need to check the smallest element
  for (var i = sortedList.length-1; i > 0; i--) {
    var biggerElement = sortedList[i];

    //You only need to iterate over smaller elements
    for(var j = 0; j < i; j++){
      var smallerElement = sortedList[j];

      //You can get rid of the '!=' check
      if((biggerElement & smallerElement) == smallerElement){
        supersetList.push(biggerElement);

        //You can break after it is determined that it is a subset
        break;
      }
    }
  }

  //If the smallest two are duplicates (which are a subset by the logic given), add the smallest
  if(sortedList.length >= 2 && sortedList[0] == sortedList[1]){
    supersetList.push(sortedList[0]);
  } 


  return supersetList;
};