s******n
发帖数: 21 | 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****n
发帖数: 1379 | 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******n
发帖数: 21 | |
s******n
发帖数: 21 | |
A*********r
发帖数: 564 | 5 怎么看起来像DP的样子，算法复杂度要O(n*m), 可能有更简单的？
【在 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"
: 要求打印出所有可能 这题怎么做? 谢谢!
|
A*********r
发帖数: 564 | 6 给个总结？
【在 s******n 的大作中提到】
: 谢谢了 刚刚悟到了
|
s*****e
发帖数: 16824 | 7 应该是(n,m+n+1)的组合数，似乎没有简单的方法，只能把组合一个一个列出来。
【在 A*********r 的大作中提到】
: 怎么看起来像DP的样子，算法复杂度要O(n*m), 可能有更简单的？
|
h**k
发帖数: 3368 | 8 和生成一个字符所有combination的算法类似。
使用递归。
在输出下一个字符时，两种选择，或者从字符串1中选，或者从字符串2中选。每选择一
个字符后，移动指针，指向该字符串的下一个字符。
重复直到输出两个串中所有字符。
【在 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"
: 要求打印出所有可能 这题怎么做? 谢谢!
|
r**u
发帖数: 1567 | 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**6
发帖数: 4160 | 10 C(6, 3) = 20
以下01串中，0表示从第一个字符串中取，1表示从第二个字符串中取。
000111
001011
010011
100011
先把第一个1移到左端，然后移第二个1
001101
010101
100101
...
111000
写一个next_combination函数可以完成这些移动，不需递归。 |
|
|
r**u
发帖数: 1567 | 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*********r
发帖数: 564 | 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*********r
发帖数: 564 | 13 赞。。
唯一的问题是如果ｍ或者ｎ很大，用ｂｉｔ ｖｅｃｔｏｒ表示有可能会溢出吧，尤其
如果需要用ｂｉｔ操作来生成下一个数的话。。
不知道还有其它的办法来生成下一个ｃｏｍｂｉｎａｔｉｏｎ么？
【在 h**6 的大作中提到】
: C(6, 3) = 20
: 以下01串中，0表示从第一个字符串中取，1表示从第二个字符串中取。
: 000111
: 001011
: 010011
: 100011
: 先把第一个1移到左端，然后移第二个1
: 001101
: 010101
: 100101
|
k***g
发帖数: 58 | 14 不用递归，移动1是怎么实现的？不能单纯的向左移动一个1吧……
比方说011001是通过什么得到的？ |
h**6
发帖数: 4160 | 15 从左向右，找到第一个1，如果可以左移就移动，然后结束。
如果不能左移，就继续向右找，找到第一个可以左移的1，左移1位，左边全部的1都向
右移动靠着刚移动过的1。
如果所有的1都不能左移，说明组合已经全部列出。
这些操作我是用x[0]=1, x[1]=0, ..., 来表示的，比用位运算更方便。 |
