打孔/将多个string合并为一个(最短的)string,其中包含每个string的所有字符

我的目的是将多个string打成一个单一的(最短的)string,该string将包含每个string的正向的所有字符。 这个问题不是特定于任何语言,而是更多地涉及algorithm部分。 (可能会在节点服务器中实现它,所以标记nodejs/javascript )。

所以,要解释这个问题:

让我们考虑一下我有几个string

 ["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"] 

结果string应该是这样的:

 "sjmachppoalidveonrk" 

jack:s j m ac hppoalidveonr k

apple:sjm a ch pp oa l idv e onrk

固体:jmachpp o 盖子 veonrk

==================================== >>>>全部在前进的方向

这些都是人工评估,在这个例子中输出可能不是100%完美。

所以,重点是每个string的所有字母都必须存在于FORWARD DIRECTION的输出中(这里是实际的问题所在),并且服务器可能会发送最终的string,并且会生成27594这样的27594并将其传递以提取令牌,在要求的最后。 如果我不得不用最小的string来打出它,那么会更容易(这种情况下只有唯一的字符就足够了)。 但在这种情况下,有一些要点:

  1. 字母可以多次出现,尽pipe我必须重用任何字母(如果可能的话),例如:for solidhold o > l > d可以作为前向重用,但对于applea > p )和sparkp > a )我们不得不重复a就像在p之前出现apple ,在p之后出现sparks所以要么重复a ,要么重复a 。 我们不能做p > a > p ,因为它将涵盖两种情况,因为我们需要两个p

  2. 我们没有select放置一个单一的p并在提取时使用相同的索引两次,我们需要多个p ,没有选项剩下的input令牌包含

  3. 我(不确定),有一组string可能有多个输出。 但是关心的是它的长度应该是最小的,这个组合并不重要,如果它覆盖所有的令牌在前进的方向。 所有(或一个)可能长度最短的输出都需要跟踪。
  4. 添加这一点作为编辑到这个职位。 在阅读了这些注释之后,我们知道已经存在的一个已知问题是最短公共超序列问题,我们可以定义结果string是最短的string,我们可以通过简单地删除一些(0到N)字符,这是相同的,因为所有的input可以在结果string中的正向中find。

我试着用一个任意string开始,然后对下一个string进行分析并分割所有的字母,并相应地放置它们,但是有些时候,似乎当前的string可以放在更好的位置,If最后一个string(或之前的string)字母是根据当前string放置的。 但是这个string再一次被分析,并且根据(多个)被处理的东西进行分析和放置,并且对某些没有被处理的东西进行处理似乎很困难,因为我们需要处理这些东西。 或者可能我维护所有已处理/未处理的树的树会有所帮助,build设最后的string? 任何比它更好的方式,这似乎是一个蛮力!

注意 :我知道还有很多其他的转换可能,请尽量不要提出任何其他的使用,我们正在做一些研究,任何问题的背景下将受到高度赞赏。 如果有什么不清楚或需要进一步的解释可以随意评论。 感谢大家耐心地阅读整个问题。

       

网上收集的解决方案 "打孔/将多个string合并为一个(最短的)string,其中包含每个string的所有字符"

我想出了一个有点蛮力的方法。 这种方式find组合2个单词的最佳方式,然后为数组中的每个元素。

这种策略通过尝试find将两个单词组合在一起的最佳方式起作用。 通过使用最less的字母被认为是最好的。 每个单词都被input到一个不断增长的“合并”单词中。 每次添加一个新单词时,都会search现有单词,以find要合并的单词中存在的匹配字符。 一旦发现一个被分成两组,并试图join(使用手头的规则,如果信件已经存在等,不需要添加2)。 该策略通常会产生良好的结果。

join_word方法需要2个单词你想join,第一个参数被认为是你join_word字。 然后search最好的方法分裂into两个单独的部分合并在一起,它通过查找任何共享的通用字符。 这是splits_on_letter方法的来源。

splits_on_letter方法需要一个单词和一个你想要分割的字母,然后返回在该字符上分割所有可能左右两边的二维数组。 例如splits_on_letter('boom', 'o')会返回[["b","oom"],["bo","om"],["boo","m"]] ,这是所有我们如何使用字母o作为分割点的组合。


sort()在开头就是试图把元素放在一起。 合并元素的顺序通常影响结果长度。 我尝试的一种方法是根据他们使用的常用字母(与他们的同龄人)进行sorting,但结果是不同的。 然而,在我所有的testing中,我可能会用5或6个不同的单词集进行testing,可能会出现更大,更多不同的单词数组,您可能会发现不同的结果。

输出是

 spmjhooarckpplivden 

 var words = ["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"]; var result = minify_words(words); document.write(result); function minify_words(words) { // Theres a good sorting method somewhere which can place this in an optimal order for combining them, // hoever after quite a few attempts i couldnt get better than just a regular sort... so just use that words = words.sort(); /* Joins 2 words together ensuring each word has all its letters in the result left to right */ function join_word(into, word) { var best = null; // straight brute force each word down. Try to run a split on each letter and for(var i=0;i<word.length;i++) { var letter = word[i]; // split our 2 words into 2 segments on that pivot letter var intoPartsArr = splits_on_letter(into, letter); var wordPartsArr = splits_on_letter(word, letter); for(var p1=0;p1<intoPartsArr.length;p1++) { for(var p2=0;p2<wordPartsArr.length;p2++) { var intoParts = intoPartsArr[p1], wordParts = wordPartsArr[p2]; // merge left and right and push them together var result = add_letters(intoParts[0], wordParts[0]) + add_letters(intoParts[1], wordParts[1]); if(!best || result.length <= best.length) { best = result; } } } } // its possible that there is no best, just tack the words together at that point return best || (into + word); } /* Splits a word at the index of the provided letter */ function splits_on_letter(word, letter) { var ix, result = [], offset = 0;; while((ix = word.indexOf(letter, offset)) !== -1) { result.push([word.substring(0, ix), word.substring(ix, word.length)]); offset = ix+1; } result.push([word.substring(0, offset), word.substring(offset, word.length)]); return result; } /* Adds letters to the word given our set of rules. Adds them starting left to right, will only add if the letter isnt found */ function add_letters(word, addl) { var rIx = 0; for (var i = 0; i < addl.length; i++) { var foundIndex = word.indexOf(addl[i], rIx); if (foundIndex == -1) { word = word.substring(0, rIx) + addl[i] + word.substring(rIx, word.length); rIx += addl[i].length; } else { rIx = foundIndex + addl[i].length; } } return word; } // For each of our words, merge them together var joinedWords = words[0]; for (var i = 1; i < words.length; i++) { joinedWords = join_word(joinedWords, words[i]); } return joinedWords; } 

第一次尝试,没有真正优化(缩短183%):

 function getShort(arr){ var perfect=""; //iterate the array arr.forEach(function(string){ //iterate over the characters in the array string.split("").reduce(function(pos,char){ var n=perfect.indexOf(char,pos+1);//check if theres already a possible char if(n<0){ //if its not existing, simply add it behind the current perfect=perfect.substr(0,pos+1)+char+perfect.substr(pos+1); return pos+1; } return n;//continue with that char },-1); }) return perfect; } 

在行动


这可以通过简单地运行上面的代码来改进一些arrays(200%的改进):

 var s=["jack",...]; var perfect=null; for(var i=0;i<s.length;i++){ //shift s.push(s.shift()); var result=getShort(s); if(!perfect || result.length<perfect.length) perfect=result; } 

在行动

这非常接近估计的最小字符数 (在最好的情况下可能有244%的最小化)

我也写了一个函数来获取最less的字符数量和一个来检查某个单词是否失败,你可以在这里find它们

我已经使用dynamic规划的思想,首先产生OP中所述的最短可能的string。 然后,我将上一步获得的结果与列表中的下一个string一起作为参数发送。 下面是java的工作代码。 希望这将有助于达到最佳的解决scheme,以防万一我的解决scheme被认定为非最佳。 请随时举报以下代码的任何反案:

 public String shortestPossibleString(String a, String b){ int[][] dp = new int[a.length()+1][b.length()+1]; //form the dynamic table consisting of //length of shortest substring till that points for(int i=0;i<=a.length();i++){ for(int j=0;j<=b.length();j++){ if(i == 0) dp[i][j] = j; else if(j == 0) dp[i][j] = i; else if(a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = 1+dp[i-1][j-1]; else dp[i][j] = 1+Math.min(dp[i-1][j],dp[i][j-1]); } } //Backtrack from here to find the shortest substring char[] sQ = new char[dp[a.length()][b.length()]]; int s = dp[a.length()][b.length()]-1; int i=a.length(), j=b.length(); while(i!=0 && j!=0){ // If current character in a and b are same, then // current character is part of shortest supersequence if(a.charAt(i-1) == b.charAt(j-1)){ sQ[s] = a.charAt(i-1); i--; j--; s--; } else { // If current character in a and b are different if(dp[i-1][j] > dp[i][j-1]){ sQ[s] = b.charAt(j-1); j--; s--; } else{ sQ[s] = a.charAt(i-1); i--; s--; } } } // If b reaches its end, put remaining characters // of a in the result string while(i!=0){ sQ[s] = a.charAt(i-1); i--; s--; } // If a reaches its end, put remaining characters // of b in the result string while(j!=0){ sQ[s] = b.charAt(j-1); j--; s--; } return String.valueOf(sQ); } public void getCombinedString(String... values){ String sSQ = shortestPossibleString(values[0],values[1]); for(int i=2;i<values.length;i++){ sSQ = shortestPossibleString(values[i],sSQ); } System.out.println(sSQ); } 

驱动程序:

 e.getCombinedString("jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"); 

输出:

jmapphsolivecparkonidr

上述解决scheme的最坏情况时间复杂度为O(product of length of all input strings)当所有string都具有不同的字符时,即使任何一对string之间没有单个字符匹配。

这是一个基于JavaScript的dynamic编程的最佳解决scheme,但它只能在内存耗尽之前,在计算机上实现。 它不同于@ CodeHunter的解决scheme,因为它在每个添加的string之后保留整套最佳解决scheme,而不仅仅是其中之一。 你可以看到最优解的数量呈指数增长, 即使在solid之后,已经有518,640个最佳解决scheme。

 const STRINGS = ["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"] function map(set, f) { const result = new Set for (const o of set) result.add(f(o)) return result } function addAll(set, other) { for (const o of other) set.add(o) return set } function shortest(set) { //set is assumed non-empty let minLength let minMatching for (const s of set) { if (!minLength || s.length < minLength) { minLength = s.length minMatching = new Set([s]) } else if (s.length === minLength) minMatching.add(s) } return minMatching } class ZipCache { constructor() { this.cache = new Map } get(str1, str2) { const cached1 = this.cache.get(str1) if (!cached1) return undefined return cached1.get(str2) } set(str1, str2, zipped) { let cached1 = this.cache.get(str1) if (!cached1) { cached1 = new Map this.cache.set(str1, cached1) } cached1.set(str2, zipped) } } const zipCache = new ZipCache function zip(str1, str2) { const cached = zipCache.get(str1, str2) if (cached) return cached if (!str1) { //str1 is empty, so only choice is str2 const result = new Set([str2]) zipCache.set(str1, str2, result) return result } if (!str2) { //str2 is empty, so only choice is str1 const result = new Set([str1]) zipCache.set(str1, str2, result) return result } //Both strings start with same letter //so optimal solution must start with this letter if (str1[0] === str2[0]) { const zipped = zip(str1.substring(1), str2.substring(1)) const result = map(zipped, s => str1[0] + s) zipCache.set(str1, str2, result) return result } //Either do str1[0] + zip(str1[1:], str2) //or str2[0] + zip(str1, str2[1:]) const zip1 = zip(str1.substring(1), str2) const zip2 = zip(str1, str2.substring(1)) const test1 = map(zip1, s => str1[0] + s) const test2 = map(zip2, s => str2[0] + s) const result = shortest(addAll(test1, test2)) zipCache.set(str1, str2, result) return result } let cumulative = new Set(['']) for (const string of STRINGS) { console.log(string) const newCumulative = new Set for (const test of cumulative) { addAll(newCumulative, zip(test, string)) } cumulative = shortest(newCumulative) console.log(cumulative.size) } console.log(cumulative) //never reached