Эффективный способ генерации комбинаций в объекте c

Question

Я ищу способ генерации комбинаций объектов из набора заданных объектов, порядок не имеет значения (НЕ перестановки, а комбинации), например. сказать. У меня есть список A, B, C, D, и мне нужно выбрать 3 из них .. то я должен получить список

ABC ДСА BCD

есть эффективная логика сделать так в объективе C?

Answer 1

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

1) Пуск при первых п элементах
2) приращению последнего элемента до тех пор, пока в конечном положении
3) Перемещение предыдущего элемента вперед на один, и сброс последнего элемента, в положение после предыдущего элемента
4) Повторите шаги 2 и 3 до тех пор, пока предыдущий элемент и последний элемент не находятся в последних двух положениях
5) Переместите предыдущий элемент вперед на 1 и сбросьте два элемента в конце позиции после предыдущего предыдущего элемента
6) повторите этот процесс до тех пор, пока все элементы не будут в конце

Упрощенная становится это:

В то время как первый элемент массива комбо меньше, чем разница между исходным массивом и массивом комбо выполнить следующие действия:

В то время как последний элемент из combo array меньше, чем длина отсчета исходного элемента массива, увеличивающего последний элемент, и принимает полученные индексы из исходного массива

После этого проверьте предыдущий элемент. Если он меньше, чем lastElement -1, то увеличьте его и установите lastElement на предыдущий элемент + 1 и повторите вышеуказанный шаг. Если нет, проверьте предыдущий элемент и т. Д. Если они все последовательны, то вы закончите.

Чтобы помочь в этом алгоритме, я предлагаю создать массив индексов, соответствующий размеру вашей комбинации. Предположим, вам нужны 3-элементные комбинации 5-элементного массива. Сделайте 3 элемента массив из первых индексов:

[0,1,2]

Применяя алгоритм выше первого не будет увеличивать последний элемент до конца [0,1,3] [ 0,1,4]

Тогда приращение предыдущего и сброшено окончательным [0,2,3]

Повторите описанные выше шаги до тех пор, два последних находятся в конечных положениях [ 0,2,4] [ 0,3,4]

Перемещение вдоль линии [1,2,3] [1,2,4] [1,3,4] [2,3,4], а теперь все индексы находятся в конечной позиции, и вы закончили.

Я не собираюсь писать это в Objective-C, хотя, поскольку реализация алгоритма - это то, что требуется от каждого программиста. Я думаю, что для этого вам будет достаточно информации.

Answer 2

Да, у вас есть. Это не сложно, но долго. Только вы должны взять за циклы для подсчета символов. Просто см. Ниже код.

NSMutableArray *arr_Combinations = [[NSMutableArray alloc] init]; 


NSString *str_First; 
NSString *str_Second; 
NSString *str_Third; 

for (NSInteger firCount = 0; firCount < 4; firCount++) 
{ 
    NSMutableArray *arr_First = [NSMutableArray arrayWithObjects:@"A", @"B", @"C", @"D", nil]; 
    str_First = [arr_First objectAtIndex:firCount]; 

    [arr_First removeObjectAtIndex:firCount]; 

    for (NSInteger secCount = 0; secCount < [arr_First count]; secCount++) 
    { 
     NSMutableArray *arr_Second = [[NSMutableArray alloc] initWithArray:arr_First]; 
     str_Second = [str_First stringByAppendingString:[arr_Second objectAtIndex:secCount]]; 
     [arr_Second removeObjectAtIndex:secCount]; 
     for (NSInteger thirCount = 0; thirCount < [arr_Second count]; thirCount++) 
     { 
      NSMutableArray *arr_Third = [[NSMutableArray alloc] initWithArray:arr_Second]; 
      str_Third = [str_Second stringByAppendingString:[arr_Third objectAtIndex:thirCount]]; 
      [arr_Third removeObjectAtIndex:thirCount]; 
      for (NSInteger fothCount = 0; fothCount < [arr_Third count]; fothCount++) 
      { 
       NSString *str_Final = [str_Third stringByAppendingString:[arr_Third objectAtIndex:fothCount]]; 
       NSLog(@"%@", str_Final); 
       [arr_Combinations addObject:str_Final]; 
      } 
     } 
    } 
} 
NSLog(@"%d", [arr_Combinations count]);