セミコロン配列のすべての可能な順列/組み合わせの生成

Question

NSArray内に2つの可能なエントリ（XまたはY）しかないことを考えれば、可能なすべてのNSArrayを生成する最良の方法は何ですか？配列の値の一部は、開始する前にすでに割り当てられているため、変更することはできません。

例えば、配列は16個の可能な順列を持ち、位置1と2はそれぞれX & Yにロックされており、変更することはできません。位置0はXまたはYをとることができますが、空にすることはできません。賢明なポジション3,4,5のように。

0:[ ] 1:[X] 2:[Y] 3:[ ] 4:[ ] 5:[ ]

[]ちょうどので、すべての順列を計算する際にXまたはYのいずれかを割り当てる必要がありますアレイ内のその位置に割り当てられたものを意味しません。その1次元配列またはサイズ6 iOSデバイスのObjective-Cでコーディングしています。ここのガイダンスは高く評価されます。 -

おかげC

Answer 1

は、私はあなたのために行っているかを理解思う：長さ2のセットから選ばれた6つのオブジェクトの順列を生成する（「X」@と@「Y」）与えられたとものを除きますパターン。

ここには、長さ2のセットから選択された6つのオブジェクトの64個の置換しかないので、ここではスピード/スペースのトレードオフが良好です。完全なセットは早く計算され、手元に保管されるほど十分です。これにより、アルゴリズムは、「固定」位置のパターンに対して単純なフィルタであることが分かります。

パターンを表す方法が必要です。 NSArraysはC配列のような定位置ではありません。カウント6の配列には、すべてのインデックス1..5にオブジェクトが含まれていなければなりません。簡単なアプローチは、「固定されていない」位置を表す別のオブジェクトを選択することです（「[]」のOP相当）。我々は@"*"、（NSNullインスタンスは、あまりにも、まともな選択である）を使用した場合、OP除外パターンは、このリテラルのようになります。

@[ @"*", @"X", @"Y", @"*", @"*", @"*" ] 

だから順列の完全なセットで始めることができます。 （その後、キャッシュされた結果を返し、その後、最初の呼び出しの計算とキャッシュ）これらなまけを計算：

@property(strong,nonatomic) NSArray *permutations; 

- (NSArray *)permutations { 
    if (!_permutations) { 
     NSSet *set = [NSSet setWithArray:@[ @"X", @"Y"]]; 
     _permutations = [self permute:set count:6]; 
    } 
    return _permutations; 
} 

// simple recursive algorithm to permute 
- (NSArray *)permute:(NSSet *)set count:(NSInteger)count { 
    NSMutableArray *result = [@[] mutableCopy]; 
    if (count == 1) { 
     for (id object in [set allObjects]) [result addObject:@[object]]; 
     return result; 
    } else { 
     NSArray *smaller = [self permute:set count:count-1]; 
     for (id object in [set allObjects]) { 
      for (NSArray *array in smaller) { 
       NSMutableArray *m = [array mutableCopy]; 
       [m insertObject:object atIndex:0]; 
       [result addObject:m]; 
      } 
     } 
     return result; 
    } 
} 

これは、のような順列を生成します...

@[ @[ @"X", @"X", @"X", @"X", @"X", @"X" ], 
    @[ @"X", @"X", @"X", @"X", @"X", @"Y" ], // ... and so on 

あなたも、コンパイル時にこれを行うことができますその結果を64要素の配列リテラルとしてアプリに含めます。

これで、問題はフィルタに減少します。ここでは（ワイルドカードとして@「*」を使用して）指定された配列がパターンにマッチするかどうかのテストがあります：

- (BOOL)array:(NSArray *)array matchesPattern:(NSArray *)pattern { 
    for (NSInteger i=0; i<array.count; i++) { 
     if (![pattern[i] isEqualToString:@"*"] && ![array[i] isEqualToString:pattern[i]]) return NO; 
    } 
    return YES; 
} 

は、述語として、そのフィルタを適用します

NSArray *pattern =@[ @"*", @"X", @"Y", @"*", @"*", @"*" ]; 
NSPredicate *predicate = [NSPredicate predicateWithBlock:^BOOL(id evaluatedObject, NSDictionary * bindings) { 
    NSArray *a = (NSArray *)evaluatedObject; 
    return [self array:a matchesPattern:pattern]; 
}]; 

とフィルタリングを実行します。

NSArray *permutations = [self permutations]; 
NSArray *result = [permutations filteredArrayUsingPredicate:predicate]; 

私はこれをOPパラメータといくつかのバリエーションでテストしました。