标签: intersection

我有两个字符串,我想在它们上面有交集,包括重复的项目:

str_a = "aabbcc"
str_b = "aabd"

list(set(str_a) & set(str_b))
>> "ab"

我想让它回归:

>> "aab"

有任何想法吗？

我以为我明白了Intersect,但事实证明我错了.

 List<int> list1 = new List<int>() { 1, 2, 3, 2, 3};
 List<int> list2 = new List<int>() { 2, 3, 4, 3, 4};

 list1.Intersect(list2) =>      2,3

 //But what I want is:
 // =>  2,3,2,3,2,3,3

我可以想办法:

 var intersected = list1.Intersect(list2);
 var list3 = new List<int>();
 list3.AddRange(list1.Where(I => intersected.Contains(I)));
 list3.AddRange(list2.Where(I => intersected.Contains(I)));

在LINQ中有更简单的方法来实现这一目标吗？

我需要说明我不关心结果的顺序.

2,2,2,3,3,3,3也可以.

问题是我在一个非常大的集合中使用它,所以我需要效率.

我们谈论的是对象,而不是整体.这些仅仅是为了简单的例子,但我意识到这可以有所作为.

有没有任何功能可以给我一个Polygon和Line2D？的交点？

我有一个Polygon和一个我知道相交的线段我希望交点的实际值不是布尔答案.

我遇到了一个问题,我必须计算集合中所有对之间的交叉点.这些集合都不小于小常数k,并且我只关心两个集合是否具有大于k -1元素的交集.我不需要实际的交叉点和确切的大小,只需要它是否大于k -1.是否有一些聪明的预处理技巧或整齐的交集算法可以用来加快速度？

更多信息可用于回答问题:

• 这些集合表示大的无向稀疏图中的最大集团.集合的数量可以是数万或更多,但是大多数集合可能很小.
• 这些集合已经是每个集合的成员按递增顺序排列.实际上它们是排序列表 - 我从底层库中以这种方式接收它们以进行最大集团搜索.
• 关于集合中元素的分布(即它们是否是紧密团块),我们都不知道.
• 大多数设置交叉点可能都是空的,因此理想的解决方案是一个聪明的数据结构,可以帮助我减少必须设置的交叉点的数量.

我找到了解决方案,但希望确保我的逻辑是最有效的.我觉得有更好的方法.我有左下角的(x,y)坐标,2个矩形的高度和宽度,我需要返回第三个矩形,它们是它们的交点.我不想发布代码,因为我觉得它是作弊.

1. 我弄清楚哪个是最左边和最高的图表.
2. 我检查一个是否与另一个完全重叠,然后反向查看另一个是否与X轴上的第一个完全重叠.
3. 我检查X轴上的部分交叉点.
4. 我基本上重复Y轴的步骤2和3.
5. 我做了一些数学计算,并根据这些条件得到矩形的点.

我可能会过度思考并编写效率低下的代码.我已经参加了一个工作计划,但我想找到最适合自己知识的方法.如果有人可以同意或指出我正确的方向,那将是伟大的!

我遇到了这个小问题,而我解决这个问题的算法并不适用于所有情况.有人知道如何解决这个问题吗？

这是一个示例多边形:

例如http://img148.imageshack.us/img148/8804/poly.png

正式说明

我们有一个CW顺序列表,用于定义多边形.我们还可以查询一个点是否是一个切割点is_cut(p),在哪里p是一个给定的点.现在我们要计算由此"切割"引起的新多边形.

算法应该这样做:

输入: {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

输出:{a, c1, c2},{b, c4, c3, f, c2, c1},{d, c6, c5},{e, c3, c4, c, c5, c6}

这是我目前的算法:

follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point 
    and …

SVG中是否可以使用任何方法调用偶数两个特定元素？或者我是否需要编写很长的代码,并弄清楚它们的边界是否与复杂的数学接触？

在计算两个任意正则表达式是否有任何重叠的解决方案(假设它是可能的).

例如,这两个正则表达式可以通过强力显示没有交叉点,因为这两个解决方案集是可计算的,因为它是有限的.

^1(11){0,1000}$ ?     ^(11){0,1000}$        = {}
{1,111, ..., ..111} ? {11,1111, ..., ...11} = {}
{}                                          = {}

但用{0,1000}通过*删除一个蛮力解决方案的可能性,所以一个更聪明的算法必须创建.

^1(11)*$ ? ^(11)*$ = {}
{1,^1(11)*$} ? {^(11)*$} = {}
{1,^1(11)*$} ? {11,^11(11)*$} = {}
{1,111,^111(11)*$} ? {11,^(11)*$} = {}
.....

在另一个类似的问题中,一个答案是计算交集正则表达式.这可能吗？如果是这样,怎么会写一个算法来做这样的事情？

我认为这个问题可能是暂停问题的结果.

编辑:

我已经使用已接受的解决方案为示例问题创建了DFA.可以很容易地看到如何在状态图上使用BFS或DFS M_3来确定是否可以达到最终状态M_3.

我有2个数据帧:

dat:1900个隐含的9个变量

              V1        V2        V3        V4 V5      V6       V7     V8             V9
1        V_P50P50_Q3 chr12 106642383 106642395  + 18.1425 4.03e-08 0.0515  GGGGGACTCCCCC
2 V_P50RELAP65_Q5_01  chr8 142276666 142276677  - 16.6429 2.51e-07 0.2780   GGGATTTCCCAC
3          V_RELA_Q6 chr22  51020067  51020078  - 15.9395 2.71e-07 0.3350   GGGAATTTCCCC
4       V_NFKB_Q6_01 chr14  98601454  98601469  + 17.0684 3.08e-07 0.236  GGAGTGGAAATTCC
5          V_CREL_Q6 chr22  51020068  51020079  - 16.1165 3.19e-07 0.4050   AGGGAATTTCCC

dat.markov:986个变量的1486个障碍物

            V1    V2        V3        V4 V5      V6       V7    V8               V9
1 V_NFKB_Q6_01 chr14  98601454  98601469  + 17.2212 1.33e-07 0.146 …

在C++中找到两个范围的交集的最佳方法是什么？例如,如果我有一个范围为[1 ... 20],包括[13 ... 45],则我想得到[13 ... 20],因为这是它们之间的交集.

我想过在C++中使用本机集合交集函数,但我首先要将范围转换为集合,这对于大值需要花费太多的计算时间.