求助字符串交叉生成的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求助字符串交叉生成的问题

求助字符串交叉生成的问题# JobHunting - 待字闺中

s*n2010-09-24 07:09

1 楼

两个字符串 "ABC" "XYZ", 请问如何生成 all possible interleaved combinations
include all character from both sets but still keep the order from their
original forms
sample output:
"AXBCYZ"
"ABXYCZ"
要求打印出所有可能这题怎么做? 谢谢!

z*n2010-09-24 07:09

2 楼

用二进制实现6选3

【在 s******n 的大作中提到】

: 两个字符串 "ABC" "XYZ", 请问如何生成 all possible interleaved combinations
: include all character from both sets but still keep the order from their
: original forms
: sample output:
: "AXBCYZ"
: "ABXYCZ"
: 要求打印出所有可能这题怎么做? 谢谢!

s*n2010-09-24 07:09

3 楼

多谢回复能再具体解释一下吗?

s*n2010-09-24 07:09

4 楼

谢谢了刚刚悟到了

A*r2010-09-24 07:09

5 楼

怎么看起来像DP的样子，算法复杂度要O(n*m), 可能有更简单的？

【在 s******n 的大作中提到】

A*r2010-09-24 07:09

6 楼

给个总结？

【在 s******n 的大作中提到】

: 谢谢了刚刚悟到了

s*e2010-09-24 07:09

7 楼

应该是(n,m+n+1)的组合数，似乎没有简单的方法，只能把组合一个一个列出来。

【在 A*********r 的大作中提到】

: 怎么看起来像DP的样子，算法复杂度要O(n*m), 可能有更简单的？

h*k2010-09-24 07:09

8 楼

和生成一个字符所有combination的算法类似。
使用递归。
在输出下一个字符时，两种选择，或者从字符串1中选，或者从字符串2中选。每选择一
个字符后，移动指针，指向该字符串的下一个字符。
重复直到输出两个串中所有字符。

【在 s******n 的大作中提到】

r*u2010-09-24 07:09

9 楼

s0 = "ABC", s1 = "XYZ";
为保证order，每次都取s0 or s1第一个字符，然后s0++ or s1++（这个就像merge
sort）。
然后递归，until all chars are used (filled into output)。
O(2^(m+n))。
楼上那个DP，O(n*n)怎么出来的？能说说么
int geneInterleave(char *s0, char *s1, char *out, int level, int slen) {
if (s0 == NULL || s1 == NULL || out == NULL || level < 0) {
printf("Invalid Input!\n");
return -1;
}
if (level == slen) {
out[level] = '\0';
printf("%s\n", out);

【在 s*****e 的大作中提到】

: 应该是(n,m+n+1)的组合数，似乎没有简单的方法，只能把组合一个一个列出来。

h*62010-09-24 07:09

10 楼

C(6, 3) = 20
以下01串中，0表示从第一个字符串中取，1表示从第二个字符串中取。
000111
001011
010011
100011
先把第一个1移到左端，然后移第二个1
001101
010101
100101
...
111000
写一个next_combination函数可以完成这些移动，不需递归。

r*u2010-09-24 07:09

11 楼

I get it. Very good solution.

【在 h**6 的大作中提到】

: C(6, 3) = 20
: 以下01串中，0表示从第一个字符串中取，1表示从第二个字符串中取。
: 000111
: 001011
: 010011
: 100011
: 先把第一个1移到左端，然后移第二个1
: 001101
: 010101
: 100101

A*r2010-09-24 07:09

12 楼

我觉得我们对题目的理解不一样。。
给一个简单的例子：s0="AB", s1="XY"
按照原题的意思，一共有6种可能性
AXBY
AXYB
ABXY
XABY
XAYB
XYAB
用DP的话，取F(i,j)表示以第一个字符串中前i个字符和第二个字符串中前j个字符的字串的可能性， F(1,j)=j+1, F(i,1)=i+1;
F(i,j)=F(i-1,j)+(F(i,j-1).
算法复杂度，应该是Ｏ（ｍ＊ｎ）因为对每个ｉ，ｊ都要算一次。
这个正好跟Ｃ（ｍ＋ｎ，ｉ）＝Ｃ（ｍ＋ｎ－１，ｉ－１）＋Ｃ（ｍ＋ｎ－１，ｉ）的
递归公式一致。

【在 r**u 的大作中提到】

: s0 = "ABC", s1 = "XYZ";
: 为保证order，每次都取s0 or s1第一个字符，然后s0++ or s1++（这个就像merge
: sort）。
: 然后递归，until all chars are used (filled into output)。
: O(2^(m+n))。
: 楼上那个DP，O(n*n)怎么出来的？能说说么
: int geneInterleave(char *s0, char *s1, char *out, int level, int slen) {
: if (s0 == NULL || s1 == NULL || out == NULL || level < 0) {
: printf("Invalid Input!\n");
: return -1;

A*r2010-09-24 07:09

13 楼

赞。。
唯一的问题是如果ｍ或者ｎ很大，用ｂｉｔ　ｖｅｃｔｏｒ表示有可能会溢出吧，尤其
如果需要用ｂｉｔ操作来生成下一个数的话。。
不知道还有其它的办法来生成下一个ｃｏｍｂｉｎａｔｉｏｎ么？

【在 h**6 的大作中提到】