Перечисление всех возможных перестановок в объекте c -xcode

Question

Я хочу, чтобы моя программа охватывала все возможные комбинации чего-то вроде 5c1,5c2,5c3 и т. Д. И вычисляла некоторые вещи в цикле.

Что-то вроде 5с1 -> 1,0,0,0,0 0,1,0,0,0 0,0,1,0,0 0,0,0,1,0 0,0,0,0,1 (5 способов)

5c2 -> 1,2,0,0,0 1,0,2,0,0 1,0,0,2 , 0 1,0,0,0,2 2,1,0,0,0 0,1,2,0,0 0,1,0,2,0 0,1,0,0 , 2 2,0,1,0,0 0,2,1,0,0 0,0,1,2,0 0,0,1,0,2 2,0,0,1,0 0,2,0,1,0 0,0,2,1,0 0,0,0,1,2 2,0,0,0,1 0,2,0,0,1 0,0,2,0,1 0,0,0,2,1 (20 способов) но 1,2,0,0,0 = 2,1,0,0,0 таким образом мы получаем 10 способов

5c3 -> 1,2,3,0,0 0 , 2,3,1,0 0,2,3,0,1 и т. Д. Упрощает 10 способов

, поэтому я пытаюсь петли, чтобы найти al l комбинации для общего nCr-> n!/[r! * (n-r)!)

Я зациклился на том, как это сделать в коде. Я использую Xcode, цель c. Я вижу, что существует метод перечисления, но он кажется чем-то другим. Любые указатели будут очень благодарны.

Answer 1

Я написал класс в C# для обработки общих функций для работы с биномиальным коэффициентом, который классифицируется по формуле n!/(n! * (n-k)!). Он выполняет следующие задачи:

1. Вывод всех K-указателей в хорошем формате для любого N выбирает K в файл. K-индексы могут быть заменены более описательными строками или буквами.

2. Преобразует K-индексы в соответствующий лексикографический указатель или ранг записи в таблице отсортированных биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, основанные на итерации. Он делает это, используя математическое свойство, присущее Треугольнику Паскаля, и является очень эффективным по сравнению с итерацией по множеству.

3. Преобразует индекс в таблицу отсортированных биномиальных коэффициентов в соответствующие K-индексы. Я считаю, что это также быстрее, чем более старые итерационные решения.

4. Использование метода Mark Dominus для вычисления биномиального коэффициента, который значительно реже переполняется и работает с большими числами.

5. Класс написан на .NET C# и предоставляет способ управления объектами, связанными с проблемой (если есть), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое, когда true, создаст общий список для хранения объектов, которые будут управляться. Если это значение ложно, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы использовать 4 вышеуказанных метода. Для доступа к таблице предоставляются методы доступа.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был широко протестирован с 2 случаями, и нет известных ошибок.

Чтобы прочитать об этом классе и загрузить код, см. Tablizing The Binomial Coeffieicent.

Следующий код будет протестировано перебирать каждую уникальную комбинацию:

public void Test10Choose5() 
{ 
    String S; 
    int Loop; 
    int N = 10; // Total number of elements in the set. 
    int K = 5; // Total number of elements in each group. 
    // Create the bin coeff object required to get all 
    // the combos for this N choose K combination. 
    BinCoeff<int> BC = new BinCoeff<int>(N, K, false); 
    int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); 
    // The Kindexes array specifies the indexes for a lexigraphic element. 
    int[] KIndexes = new int[K]; 
    StringBuilder SB = new StringBuilder(); 
    // Loop thru all the combinations for this N choose K case. 
    for (int Combo = 0; Combo < NumCombos; Combo++) 
    { 
     // Get the k-indexes for this combination. 
     BC.GetKIndexes(Combo, KIndexes); 
     // Verify that the Kindexes returned can be used to retrive the 
     // rank or lexigraphic order of the KIndexes in the table. 
     int Val = BC.GetIndex(true, KIndexes); 
     if (Val != Combo) 
     { 
     S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString(); 
     Console.WriteLine(S); 
     } 
     SB.Remove(0, SB.Length); 
     for (Loop = 0; Loop < K; Loop++) 
     { 
     SB.Append(KIndexes[Loop].ToString()); 
     if (Loop < K - 1) 
      SB.Append(" "); 
     } 
     S = "KIndexes = " + SB.ToString(); 
     Console.WriteLine(S); 
    } 
} 

Вы должны быть в состоянии к порту этот класса над довольно легко Objective C. Вы, вероятно, не будет иметь порт по общей части класса для достижения ваших целей. В зависимости от количества комбинаций, с которыми вы работаете, вам может потребоваться использовать более крупный размер слова, чем 4 байта int.