View Problem
Subdivide A Problem To A Pool Of Workers (No Shared Data)
Take a hard to compute problem and split it up between multiple worker threads. In your solution, try to fully utilize available cores or processors. (I'm looking at you, Python!)
Note: In this question, there should be no need for shared state between worker threads while the problem is being solved. Only after every thread completes computation are the answers recombined into a single output.
Example:
-Input-
(In python syntax)
In other words, a list of random strings.
-Output-
(In python syntax)
In other words, all possible permutations of each input string are computed.
clojure
clojure 1.2.1
cpp OpenMP
fantom
fsharp
fsharp .NET 4
groovy
groovy with gpars
haskell
java
java
python python 2.7
ruby
scala 2.8
Submit a new solution for clojure, cpp, fantom, fsharp ...
Note: In this question, there should be no need for shared state between worker threads while the problem is being solved. Only after every thread completes computation are the answers recombined into a single output.
Example:
-Input-
(In python syntax)
["ab", "we", "tfe", "aoj"]
In other words, a list of random strings.
-Output-
(In python syntax)
[ ["ab", "ba", "aa", "bb", "a", "b"], ["we", "ew", "ww", "ee", "w", "e"], ...
In other words, all possible permutations of each input string are computed.
(defn perm-chars [l]
"Returns a list of all possible permutations of strings with the
same size as the input string. This function will return duplicates
if the same character occurs multiple time in the string.
Ex: ab -> (aa ab ba ab)"
(if (string? l)
(recur (repeat (count l) l))
(let [s (first l)
r (rest l)]
(if (empty? r)
(map identity s)
(->> s
(map (fn [c] (map #(str c %) (perm-chars r))))
(flatten))))))
(defn perm-sz [s]
"Returns a list of all possible permutations of the input
string. May return duplicats.
Ex: ab -> (aa ab ba bb a b a b)"
(if-not (empty? s)
(let [r (perm-chars s)]
(if (= (count s) 1)
r
(->> r
(map #(perm-sz (apply str (rest %))))
(flatten)
(lazy-cat r))))))
(defn perm [s]
"Returns a list of all possible permutations of the input
string. The list of string is sorted and does not contain
duplicates.
Ex: ab -> (a aa ab b ba bb)"
(->> (reduce (fn [s e] (conj s e)) #{} (perm-sz s))
(map str)
(sort)))
(println (pmap perm ["ab" "we" "tfe" "aoj"]))
"Returns a list of all possible permutations of strings with the
same size as the input string. This function will return duplicates
if the same character occurs multiple time in the string.
Ex: ab -> (aa ab ba ab)"
(if (string? l)
(recur (repeat (count l) l))
(let [s (first l)
r (rest l)]
(if (empty? r)
(map identity s)
(->> s
(map (fn [c] (map #(str c %) (perm-chars r))))
(flatten))))))
(defn perm-sz [s]
"Returns a list of all possible permutations of the input
string. May return duplicats.
Ex: ab -> (aa ab ba bb a b a b)"
(if-not (empty? s)
(let [r (perm-chars s)]
(if (= (count s) 1)
r
(->> r
(map #(perm-sz (apply str (rest %))))
(flatten)
(lazy-cat r))))))
(defn perm [s]
"Returns a list of all possible permutations of the input
string. The list of string is sorted and does not contain
duplicates.
Ex: ab -> (a aa ab b ba bb)"
(->> (reduce (fn [s e] (conj s e)) #{} (perm-sz s))
(map str)
(sort)))
(println (pmap perm ["ab" "we" "tfe" "aoj"]))
(require 'cojure.contrib.combinatorics)
(pmap (fn [str]
(apply concat (map #(selections str (inc %))
(range (count str)))))
["ab", "we", "tfe", "aoj"])
(pmap (fn [str]
(apply concat (map #(selections str (inc %))
(range (count str)))))
["ab", "we", "tfe", "aoj"])
vector<string> input;
input.push_back("ab");
input.push_back("we");
input.push_back("tfe");
input.push_back("aoj");
// Make the capacity for 'output' the same as 'input'
vector<set<string> > output(input.size());
#pragma omp parallel for
for (int i = 0; i < input.size(); ++i) {
set<string> perms;
generate_perms(input[i], perms);
#pragma omp critical
// Must use operator[]() and not push_back() since this line
// might be called in any order with respect to 'i'
output[i] = perms;
}
cout << output << endl;
input.push_back("ab");
input.push_back("we");
input.push_back("tfe");
input.push_back("aoj");
// Make the capacity for 'output' the same as 'input'
vector<set<string> > output(input.size());
#pragma omp parallel for
for (int i = 0; i < input.size(); ++i) {
set<string> perms;
generate_perms(input[i], perms);
#pragma omp critical
// Must use operator[]() and not push_back() since this line
// might be called in any order with respect to 'i'
output[i] = perms;
}
cout << output << endl;
using concurrent
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
const class PermGen : Actor
{
new make(ActorPool pool) : super(pool) {}
Void permutations(Str prefix, Str w, Str[] pset)
{
n := w.size
if (n == 0)
{
if (!pset.contains(prefix))
pset.add(prefix)
return
}
n.times { permutations(prefix + w[it..it], w[0..<it] + w[it+1..<n], pset) }
}
override Obj? receive(Obj? msg)
{
Str word := msg
wordSubPerm := Str[,]
for (Int i := 0; i < word.size; i++)
for (Int j := i; j < word.size; j++)
permutations("", word[i..j], wordSubPerm)
return wordSubPerm
}
}
class SolutionXX
{
static Void main()
{
pool := ActorPool() { maxThreads = 8 }
futures := Future[,]
["ab", "we", "tfe", "aoj"].each { futures.add(PermGen(pool).send(it)) }
futures.each { echo(it.get) }
}
}
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
const class PermGen : Actor
{
new make(ActorPool pool) : super(pool) {}
Void permutations(Str prefix, Str w, Str[] pset)
{
n := w.size
if (n == 0)
{
if (!pset.contains(prefix))
pset.add(prefix)
return
}
n.times { permutations(prefix + w[it..it], w[0..<it] + w[it+1..<n], pset) }
}
override Obj? receive(Obj? msg)
{
Str word := msg
wordSubPerm := Str[,]
for (Int i := 0; i < word.size; i++)
for (Int j := i; j < word.size; j++)
permutations("", word[i..j], wordSubPerm)
return wordSubPerm
}
}
class SolutionXX
{
static Void main()
{
pool := ActorPool() { maxThreads = 8 }
futures := Future[,]
["ab", "we", "tfe", "aoj"].each { futures.add(PermGen(pool).send(it)) }
futures.each { echo(it.get) }
}
}
open System
let input = [| "ab"; "we"; "tfe"; "aoj" |]
/// Computes all permutations of an array
let rec permute = function
| [| |] -> [| [| |] |]
| a ->
a
|> Array.mapi (fun i ai ->
// Take all elements in the array apart from the i.th, compute
// their permutations, then attach element i at the front of each perm
Array.sub a 0 i
|> Array.append (Array.sub a (i + 1) (a.Length - i - 1))
|> permute
|> Array.map (fun perm -> Array.append [| ai |] perm)
)
|> Array.concat
/// Computes all permutations of a string
let permuteString (s: string) =
s.ToCharArray()
|> permute
|> Array.map (fun p -> new String(p))
let output =
input
|> Array.map (fun word -> async { return (permuteString word) })
|> Async.Parallel
|> Async.RunSynchronously
let input = [| "ab"; "we"; "tfe"; "aoj" |]
/// Computes all permutations of an array
let rec permute = function
| [| |] -> [| [| |] |]
| a ->
a
|> Array.mapi (fun i ai ->
// Take all elements in the array apart from the i.th, compute
// their permutations, then attach element i at the front of each perm
Array.sub a 0 i
|> Array.append (Array.sub a (i + 1) (a.Length - i - 1))
|> permute
|> Array.map (fun perm -> Array.append [| ai |] perm)
)
|> Array.concat
/// Computes all permutations of a string
let permuteString (s: string) =
s.ToCharArray()
|> permute
|> Array.map (fun p -> new String(p))
let output =
input
|> Array.map (fun word -> async { return (permuteString word) })
|> Async.Parallel
|> Async.RunSynchronously
// like the Java and Groovy solutions, does not duplicate letters
open System
open System.Threading.Tasks
let input = [| "ab"; "we"; "tfe"; "aoj" |]
let factorial n =
seq { 1 .. n } |> Seq.reduce (*)
let swap (arr:'a[]) i j =
[| for k = 0 to arr.Length - 1 do
yield if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]
let rec permutation (k:int,j:int) (r:'a[]) =
if j = (r.Length + 1) then r
else permutation (k/j+1, j+1) (swap r (j-1) (k%j))
let permutations (source:'a[]) = seq {
for k = 0 to (factorial source.Length) - 1 do
yield permutation (k,2) source
}
let permute (word:string) =
let letters = word.ToCharArray()
permutations letters
|> Seq.map (fun chars -> String(chars))
|> Array.ofSeq
let tasks =
input |> Array.map (fun word -> Task.Factory.StartNew(fun () -> permute word))
let taskResult (t:Task<_>) =
t.Result
let output = Task.Factory.ContinueWhenAll(tasks, fun ts -> Array.map taskResult ts).Result
open System
open System.Threading.Tasks
let input = [| "ab"; "we"; "tfe"; "aoj" |]
let factorial n =
seq { 1 .. n } |> Seq.reduce (*)
let swap (arr:'a[]) i j =
[| for k = 0 to arr.Length - 1 do
yield if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]
let rec permutation (k:int,j:int) (r:'a[]) =
if j = (r.Length + 1) then r
else permutation (k/j+1, j+1) (swap r (j-1) (k%j))
let permutations (source:'a[]) = seq {
for k = 0 to (factorial source.Length) - 1 do
yield permutation (k,2) source
}
let permute (word:string) =
let letters = word.ToCharArray()
permutations letters
|> Seq.map (fun chars -> String(chars))
|> Array.ofSeq
let tasks =
input |> Array.map (fun word -> Task.Factory.StartNew(fun () -> permute word))
let taskResult (t:Task<_>) =
t.Result
let output = Task.Factory.ContinueWhenAll(tasks, fun ts -> Array.map taskResult ts).Result
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]
def threads = []
void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}
words.each { word ->
def t = Thread.start {
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
threads << t
}
threads.each{ it.join() }
println ans
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]
def threads = []
void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}
words.each { word ->
def t = Thread.start {
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
threads << t
}
threads.each{ it.join() }
println ans
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]
void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}
withParallelizer {
words.eachParallel { word ->
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
}
println ans
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]
void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}
withParallelizer {
words.eachParallel { word ->
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
}
println ans
import Control.Parallel
import Control.Parallel.Strategies
allPerms xs = do
x <- [1 .. length xs]
sequence (replicate x xs)
result = parMap rdeepseq allPerms ["ab", "we", "tfe", "aoj"]
main = print $ concat result
{-
Compile with -threaded
-}
import Control.Parallel.Strategies
allPerms xs = do
x <- [1 .. length xs]
sequence (replicate x xs)
result = parMap rdeepseq allPerms ["ab", "we", "tfe", "aoj"]
main = print $ concat result
{-
Compile with -threaded
-}
public class ParallelPermutations {
final AtomicInteger cnt = new AtomicInteger(0);
final List<Set<String>> permutations = new ArrayList<Set<String>>();
public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}
public ParallelPermutations(List<String> words) {
for (final String word : words) {
new Thread(new Runnable() {
public void run() {
cnt.incrementAndGet() ;
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j),
permutationSet);
permutations.add(permutationSet);
if (cnt.decrementAndGet() == 0)
synchronized (ParallelPermutations.this) {
ParallelPermutations.this.notify();
}
}
private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations);
}
}).start();
}
synchronized (this) {
try {
wait();
} catch (InterruptedException e) {
Thread.currentThread().isInterrupted();
}
}
System.out.println(permutations);
}
}
final AtomicInteger cnt = new AtomicInteger(0);
final List<Set<String>> permutations = new ArrayList<Set<String>>();
public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}
public ParallelPermutations(List<String> words) {
for (final String word : words) {
new Thread(new Runnable() {
public void run() {
cnt.incrementAndGet() ;
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j),
permutationSet);
permutations.add(permutationSet);
if (cnt.decrementAndGet() == 0)
synchronized (ParallelPermutations.this) {
ParallelPermutations.this.notify();
}
}
private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations);
}
}).start();
}
synchronized (this) {
try {
wait();
} catch (InterruptedException e) {
Thread.currentThread().isInterrupted();
}
}
System.out.println(permutations);
}
}
public class ParallelPermutations {
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};
ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);
for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());
System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}
private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();
public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}
private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}
public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));
Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();
String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}
private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}
/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}
/** the word this task is working on*/
public String getWord() {
return word;
}
/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}
/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}
/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}
final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}
/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;
/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};
ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);
for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());
System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}
private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();
public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}
private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}
public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));
Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();
String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}
private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}
/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}
/** the word this task is working on*/
public String getWord() {
return word;
}
/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}
/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}
/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}
final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}
/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;
/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}
import multiprocessing
import itertools
task_input = ["ab", "we", "tfe", "aoj"]
def all_subperms(s):
return set(reduce(
list.__add__,
([''.join(p) for p in itertools.product(s, repeat=r) if p]
for r in xrange(len(s) + 1))))
p = multiprocessing.Pool(len(task_input))
task_output = p.map(all_subperms, task_input)
print map(list, task_output)
import itertools
task_input = ["ab", "we", "tfe", "aoj"]
def all_subperms(s):
return set(reduce(
list.__add__,
([''.join(p) for p in itertools.product(s, repeat=r) if p]
for r in xrange(len(s) + 1))))
p = multiprocessing.Pool(len(task_input))
task_output = p.map(all_subperms, task_input)
print map(list, task_output)
array, threads, answers = ["ab", "we", "tfe", "aoj"], [], []
array.each { |word|
threads << Thread.new(word.split '' ) do |x|
answer = []
x.each { |a|
answer << a
x.each { |b| answer << [a, b].join }
}
answers << answer
end
}
threads.each {|thr| thr.join}
answers
array.each { |word|
threads << Thread.new(word.split '' ) do |x|
answer = []
x.each { |a|
answer << a
x.each { |b| answer << [a, b].join }
}
answers << answer
end
}
threads.each {|thr| thr.join}
answers
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
// future detaches a computation whose result can
// be applied for at a later time
import scala.actors.Futures.future
def perm(s: String): IndexedSeq[String] =
if (s.length == 1)
IndexedSeq(s)
else
s map { c =>
future {
val subperms = perm(s filter (c !=))
(subperms map (c +)) ++ subperms
}
} flatMap (_ apply ())
def perms(l: Traversable[String]) =
l map (s => future(perm(s))) map (_ apply ())
val args = Seq("ab", "we", "tfe", "aoj")
println(perms(args))
// future detaches a computation whose result can
// be applied for at a later time
import scala.actors.Futures.future
def perm(s: String): IndexedSeq[String] =
if (s.length == 1)
IndexedSeq(s)
else
s map { c =>
future {
val subperms = perm(s filter (c !=))
(subperms map (c +)) ++ subperms
}
} flatMap (_ apply ())
def perms(l: Traversable[String]) =
l map (s => future(perm(s))) map (_ apply ())
val args = Seq("ab", "we", "tfe", "aoj")
println(perms(args))
Submit a new solution for clojure, cpp, fantom, fsharp ...
