Ordering words to fit in a given string

Question

Given a string of letters and a set of words, output an ordering of the words so that they can be found in the string by dropping letters that are not needed. Words may occur more than once in the word set. The input string and all words will consist of 1 to 1000 lower case letters each. The letters to be dropped may occur inside words or between words.

Your program or function can accept the letter string and words as lists, a string, or from STDIN, and must output all words in a correct order as a list or string output. If there is more than one correct solution, only output one of them. If there is no possible correct solution, output an empty list or an empty string.

Examples:

dogcatfrog cat frog dog
-> dog cat frog

xxcatfixsxhingonxgrapexxxfishingcxat cat grape catfish fishing
-> catfish grape fishing cat

dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc
-> da ab ba ba ba cc bb aa ac dc db dd

flea antelope
->
(no solution)

This is code golf. Lowest number of bytes wins.

Edit: Explained that extra characters can be inside words.

Answer 1

Pyth, 20 24 bytes

My first attempt on Pyth :)

Jcw;FG.ptJI:hJj".*"G0jdG

How it works:

Jcw;FG.ptJI:hJj".*"G0jdG
Jcw                         assign("J",chop(input()))
    FG.ptJ                  for G in permutations(tail(J)):
          I:hJj".*"G0        if match(head(J),join(".*",G)):
                     jdG      print(join(" ",G))

Notes: it takes a long time in the third example (dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc).

Answer 2

Pyth, 10 bytes

h@s./Myz.p

Demonstration

This program is very much brute force. It first constructs every subset of the input, then every partition of the subsets, then checks for the first one which is a reordering of the word list. No possibilities is handled via erroring with no output to stdout, which is allowed by meta consensus. The error can be removed for 2 extra bytes.

Note that for many of the given test cases, the program will not complete in a reasonable period of time.

Answer 3

JavaScript (ES6), 119 bytes

(s,a,t=``,...r)=>a[0]?a.find((w,i)=>(b=[...a],b.splice(i,1),f(s,b,w+t,w,...r)))&&q:~s.search(t.split``.join`.*`)&&(q=r)

Accepts a string and an array of words and returns an array of words or undefined on failure. Add 2 bytes if it must return the empty string on failure (?q:``), in which case this alternative version is only 120 bytes and returns the empty string on failure, and can even save 2 bytes if it's allowed to return 0 on failure:

(s,a,t=``,...r)=>a[0]?a.reduce((q,w,i)=>q||(b=[...a],b.splice(i,1),f(s,b,w+t,w,...r)),0):~s.search([...t].join`.*`)?r:``

(After writing this I noticed that the algorithm is basically the same as @KennyLau's Pyth answer.)

Edited edit: updated after clarification of question, but is now really slow on the third test case; I set it off the night before last and this morning I've just noticed that it has actually found the solution, somewhere between 30 and 40 hours later. I was really mean though and fed the solution to it (it works best with the reversed solution, which it will verify instantly).

Answer 4

Java 7, 256 bytes

import java.util.*;String c(String...a){Map s=new HashMap();int j,i=1,l=a[0].length();for(;i<a.length;i++)if((j=a[0].indexOf(a[i]))>-1)s.put(j,s.get(j)!=null?s.get(j)+" "+a[i]:a[i]);a[0]="";for(j=0;j<l;j++)a[0]+=s.get(j)!=null?s.get(j)+" ":"";return a[0];}

It should definitely be possible to golf this more by using a different approach, but this will do for now..

Ungolfed & test code:

Try it here.

import java.util.*;
class M{
  static String c(String... a){
    Map s = new HashMap();
    int j,
        i = 1,
        l = a[0].length();
    for(; i < a.length; i++){
      if((j = a[0].indexOf(a[i])) > -1){
        s.put(j, s.get(j) != null
                  ? s.get(j) + " " + a[i]
                  : a[i]);
      }
    }
    a[0] = "";
    for(j = 0; j < l; j++){
      a[0] += s.get(j) != null
               ? s.get(j) + " "
               : "";
    }
    return a[0];
  }

  public static void main(String[] a){
    System.out.println(c("dogcatfrog", "cat", "frog", "dog"));
    System.out.println(c("xxcatfixsxhingonxgrapexxxfishingcxat", "cat", "grape", "catfish", "fishing"));
    System.out.println(
        c("dababbabadbaccbcbaaacdacdbdd ", "aa", "bb", "cc", "dd", "ba", "ba", "ba", "ab", "ac", "da", "db", "dc"));
    System.out.println(c("flea", "antelope"));
  }
}

Output:

dog cat frog 
cat grape fishing 
da ab ba ba ba bb db ac cc aa dd 

Answer 5

Groovy (44 Bytes)

I can't believe nobody else used regexes for this...

{a,b->a.findAll(/${b.join('|')}/).join(" ")}

Explanation

/${b.join('|')}/ - Create a regex to find any of the words in a string.
.findAll(...) - Find and collect all occurrences in the string into an array.
.join(" ") - Join the array together with spaces.

Basically, if there aren't any occurrences, the array is empty and returns an empty string implicitly. If it does find occurrences, it returns an array object with the occurrences then flattens it into a string.