рекурсивное перечисление целых подмножеств?

Question

У меня есть NSArray из NSNumbers с целочисленными значениями, такими как [1,10,3]. Я хочу получить сумму всех возможных подмножеств этих чисел. Например, для 1,10 и 3 я бы получил:

1, 10, 3, 1 + 10 = 11, 1 + 3 = 4, 10 + 3 = 13, 1 + 10 + 3 = 14

есть 2 ^ n возможных комбинаций. Я понимаю математику, но я испытываю затруднения, вставляя это в код. так как я могу поместить это в метод, который будет принимать начальный массив чисел и возвращать массив со всеми суммами подмножеств? например, -(NSArray *) getSums:(NSArray *)numbers;

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

Answer 1

Простое рекурсивное решение - возможно, несколько неэффективное, и оно не проверено, но общая идея должна быть ясной.

- (NSArray*)getSums:(NSArray*)numbers {
    return [[self getSumsHelper:numbers startingFrom:0] copy];
}

- (NSMutableArray*)getSumsHelper:(NSArray*)numbers startingFrom:(NSUInteger)index {
    /* (1) */
    if (index >= [numbers count])
        return [NSMutableArray arrayWithObject:[NSNumber numberWithFloat:0]];

    /* (2) Generate all the subsets where the `index`th element is not included */
    NSMutableArray* result = [self getSumsHelper:numbers startingFrom:index+1];

    /* (3) Add all the cases where the `index`th element is included */
    NSUInteger i, n = [result count];
    float element = [[numbers objectAtIndex:index] floatValue];
    for (i = 0; i < n; i++) {
        float element2 = [[result objectAtIndex:i] floatValue];
        [result addObject:[NSNumber numberWithFloat:element+element2]];
    }

    return result;
}

Ключом к проблеме является генерация всех подмножеств данного массива. Это можно сделать рекурсивно, признав следующее:

1. Множество подмножеств пустого массива является пустым массивом, а сумма элементов в пустом массиве равна нулю. Это обрабатывается линиями, помеченными (1).

2. Если массив не пустой, то пусть первый элемент будет X. Любое подмножество либо включает X, либо не включает его. Поэтому мы сгенерируем все подмножества массива, который не включает в себя X (есть рекурсия, отмеченная (2), вычислим суммы каждого подмножества, а затем продублируем массив сумм и добавим X к каждой из сумм в дублированная часть (отмечена (3)).

Если у вас есть только несколько элементов в исходном массиве (скажем, меньше 16), то вы также можете считать от 0 до 2 ⁿ -1 в цикле for; каждый индекс будет соответствовать подмножеству. Элементы в i -ом подмножестве можно определить, написав i в базе 2 и выбрав те элементы из массива, которые соответствуют цифре 1 в форме базы 2. Я считаю, что это даже менее эффективно, чем мое решение выше.

Answer 2

[Внимание: впереди «умный» код.Вы, вероятно, лучше делать что-то попроще.Но это довольно забавно, и о некоторых приемах стоит знать.]

Если наборы достаточно малы (что должно быть лучше, потому что в противном случае у вас не хватит памяти и времени)), вы можете использовать тот факт, что подмножества n-элементного набора == n-битных чисел.Поэтому нет необходимости в рекурсии: цикл от 0 до 1 <<p> Один из недостатков заключается в том, что для каждого подмножества вам, возможно, придется каждый раз рассматривать все его элементы с нуля.Итак, следующий прием: используйте код Грея (http://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_Gray_code), чтобы в наборе k были элементы, соответствующие 1-битам в k ^ (k >> 1). Теперь каждое подмножество отличается от своего предшественника только одним битом, который вы можетеизолировать с помощью другой операции исключающего или.

ОК, но теперь у вас есть другая проблема: у вас есть степень 2 и вы хотите знать, какому элементу массива соответствует. Так что смотрите http://www -graphics.stanford.edu / ~ seander / bithacks.html # IntegerLogLookup и посмотрите на начало бита "Если вы знаете, что v является степенью 2".

Таким образом, код в конечном итоге выглядитчто-то вроде этого (примечание: полностью не проверено) ...

static const int bitPositions[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

NSUInteger n = [numbers count];
NSUInteger lim = 1<<n;
NSUInteger k, prevSubset=0;
float prevSum = 0;
NSMutableArray * result = [NSMutableArray arrayWithCapacity: lim];
[result replaceObjectAtIndex: 0 withObject: [NSNumber numberWithFloat: prevSum]]; /* empty subset */
for (k=1; k<lim; ++k) {
  NSUInteger thisSubset = k^(k>>1);
  NSUInteger changed = thisSubset^prevSubset;
  int index = bitPositions[(changed * 0x077CB531U) >> 27];
  float delta = [[numbers objectAtIndex: index] floatValue];
  if (thisSubset&changed) prevSum += delta; else prevSum -= delta;
  [result replaceObjectAtIndex: k withObject: [prevsum floatValue]];
}

Дальнейшее предупреждение: Помимо того, что это "умный" и, следовательно, вероятно, ошибочный и не поддерживаемый, вышеприведенный код накапливает любые ошибки с плавающей точкой в ​​течение всего вычисления.Поэтому, если вы собираетесь использовать такой подход, вот лучший способ (примечание: код такой же непроверенный, как и последний лот):

static const int bitPositions[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

NSUInteger n = [numbers count];
NSUInteger lim = 1<<n;
NSUInteger k;
NSMutableArray * result = [NSMutableArray arrayWithCapacity: lim];
[result replaceObjectAtIndex: 0 withObject: [NSNumber numberWithFloat: prevSum]]; /* empty subset */
for (k=1; k<lim; ++k) {
  NSUInteger firstOne = k & ~(k-1); /* one 1-bit (as it happens, the lowest) */
  NSUInteger predecessor = k^firstOne; /* what we get by removing firstOne */
  int index = bitPositions[(firstOne * 0x077CB531U) >> 27];
  float smaller = [[result objectAtIndex: predecessor] floatValue];
  float delta = [[numbers objectAtIndex: index] floatValue];
  [result replaceObjectAtIndex: k withObject: [(smaller+delta) floatValue]];
}

Для большей эффективности, если выдействительно делаетэто, вероятно, вы начнете с создания массива, содержащего не магические битовые индексы bitPositions выше, но соответствующие значения из numbers, и, таким образом, сохраняя один доступ NSArray на подмножество.Если вы заботитесь об эффективности, то вам, вероятно, следует также скопировать numbers в простой старый C-стиль массива float s, чтобы вам никогда не приходилось вызывать floatValue.