Поиск чисел, являющихся надмножеством другого числа в списке

Число 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²). Есть ли решение более эффективное?

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


performance algorithm time-complexity bit-manipulation coding-efficiency
person Phablulo Joel    schedule 28.04.2020    source источник
comment
Когда вы говорите, что все числа являются надмножеством любого другого числа, вы имеете в виду все числа, которые являются надмножеством хотя бы одного другого числа?   -  person orlp    schedule 28.04.2020
comment
@orlp, точно.   -  person Phablulo Joel    schedule 28.04.2020
comment
Если список отсортирован, мы можем ограничить поиск a > b, но он все равно O(n^2)   -  person Damien    schedule 28.04.2020
comment
Я не вижу лучше, чем O(n^2). Но сортировка по количеству установленных битов, скорее всего, обеспечит ускорение.   -  person btilly    schedule 28.04.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

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;
};
person Briguy37    schedule 28.04.2020
comment
Спасибо за ваш ответ, но это все равно O(n²):/ - person Phablulo Joel; 28.04.2020