objective-c - 使用两个 'alphabets' 的不同长度的序列组合

Question

我正在尝试生成给定特定字母表的长度为 k 的序列的所有可能组合(这是为生物信息学项目生成查询序列)。

序列的形式是:

第一个字符和最后一个字符可以是 A C G U 中的任何一个(称之为 Y)，中间的 k - 2 个字符可以是 A C G U 中的任何一个或 ? (称这些为 X)。

例如如果 k = 3，则模式的形式为 YXY，如果 k = 5，则为 YXXXY。

如果 k 已知，生成所有可能的序列很容易，因为您只需使用 k 嵌套 for 循环。但如果事先不知道 k，则此实现不适合。

可能序列的总数可以表示为 4^2 * 5^(k-2)。当 k = 3 时，这只会给出 80 种组合，但将其扩展到 k = 9 时，您就有 1,250,000 种组合!

如有任何提示、想法或建议，我们将不胜感激。

我需要使用生成的每个序列，所以它们需要存储在一个数组中，或者在创建/生成时传递给另一个函数，哪个并不重要，尽管我不想存储所有

非常感谢。

注意我正在用 objective-c 编写，但任何 c 风格的代码、伪代码或算法的简单英语描述都会有所帮助。

更新:

这是我根据 Analog File 的精彩回答编写的 objc 代码。目前它每行只输出一个序列到标准输出，但我会修改它以生成一个字符串数组。

非常感谢所有做出贡献的人。

    NSArray *yAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", nil];
    NSArray *xAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", @"?", nil];
    int i, v;
    int count = 0;
    int numberOfCases = 16 * pow(5 , (k - 2));
    for (int n = 0; n < (numberOfCases); n++) {
        i = n;
        v = i % 4;
        i = i / 4;
        count++;
        printf("\n%s", [[yAlphabet objectAtIndex:v] cStringUsingEncoding:NSUTF8StringEncoding]);
        for (int m = 1; m < (k - 1); m++) {
            v = i % 5;
            i = i / 5;
            printf("%s", [[xAlphabet objectAtIndex:v] cStringUsingEncoding:NSUTF8StringEncoding]);
        }
        printf("%s", [[yAlphabet objectAtIndex:i] cStringUsingEncoding:NSUTF8StringEncoding]);
    }
    printf("\n");
    NSLog(@"No. Sequences: %i", count);

更新 2:

这是代码，将生成的序列输出到字符串数组。请注意，k 是所需序列的长度，并在其他地方作为参数给出。我已经测试了这个直到 k=9(1,250,000 个序列)。另请注意，我的代码使用 ARC，因此没有显示内存释放。

    NSArray *yAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", nil];
    NSArray *xAlphabet = [NSArray arrayWithObjects:@"A", @"C", @"G", @"U", @"?", nil];
    NSMutableArray *sequences = [[NSMutableArray alloc] init];
    int i, v;
    int count = 0;
    int numberOfCases = 16 * pow(5 , (k - 2));
    for (int n = 0; n < (numberOfCases); n++) {
        i = n;
        v = i % 4;
        i = i / 4;
        count++;
        NSMutableString *seq = [[NSMutableString alloc] initWithString:[yAlphabet objectAtIndex:v]];
        for (int m = 1; m < (k - 1); m++) {
            v = i % 5;
            i = i / 5;
            [seq appendString:[xAlphabet objectAtIndex:v]];
        }
        [seq appendString:[yAlphabet objectAtIndex:i]];
        [sequences addObject:seq];
    }
    NSLog(@"No. Sequences looped: %i", count);

    //print the array to confirm
    int count1 = 0;
    for (NSMutableString *str in sequences) {
        fprintf(stderr, "%s\n", [str cStringUsingEncoding:NSUTF8StringEncoding]);
        count1++;
    }
    NSLog(@"No. Sequences printed: %i", count1);
    NSLog(@"Counts match? : %@", (count == count1 ? @"YES" : @"NO"));

Answer 1

您知道您将收到多少个案例。这是伪代码(k是序列长度)

 for n = 0 to num_of_cases - 1

    i = n

    v = i % length_of_alphabeth_Y
    i = i / length_of_alphabeth_Y
    output vth char in alphabeth Y

    for m = 1 to k-1
       v = i % length_of_alphabeth_X
       i = i / length_of_alphabeth_X
       output vth char in alphabeth X

    output ith char in alphabeth Y
    output end of sequence

外循环的每次迭代都会生成一个案例。我写了 output 但很容易将数据“存储”在动态分配的结构中(roes 中的 n 个索引，第一个案例是第 0 列然后列中的 m 个索引，最后一个案例是列 k-1。如果你这样做，则不需要输出“序列结束”，因为它包含在 n 的增量中)。

请注意我们如何有效地在基 length_of_alphabeth 中“计数”，除了我们根据数字使用不同的基数。 Modulo 给出最低有效位，整数除法去掉它并将下一位移到最低有效位。

如果您可以将 n 想象成只是一个值，没有特定的基础，那么逻辑就相当简单了。一旦您理解了它，您可能可以自己从头开始编写它。