#!/bin/bash
sed 's/\(.\)/\\\1,/g' |
sed 's/.$/}\\/g' |
sed 's/^/{/g' |
sed 's/^.\(..\)..$/\1\\/g' |
sed 's!^.$! >/dev/null \\!' |
sed '1s/^/echo /' |
bash |
sed 's/ /\n/g'

-             (permute (read-lists-of-chars)))
+             (permute (let ((string (read-line)))
+                        (make-list (string-length string)
+                                   (string->list string)))))

Если немного пренебречь правилами и считать, что слова разделяются пробелами, то так:

fmap (unwords . foldM (map . flip (:)) [] . reverse . words) getLine >>= putStrLn

Если быть честным, то как-то так:

import Control.Monad

combinations = foldM (map . flip (:)) [] . reverse

main = fmap (unlines . combinations . lines) getContents >>= putStr

Слова на входе и на выходе оканчиваются переводом строки, этот символ не является частью слова.

Вторую особо красиво не получилось написать, ну да я не заморачивался. С эффективностью: надо думать, можно ли сильно лучше.

permutations xs = permutations' [] xs
  where
    permutations' [] [] = [[]]
    permutations' _  [] = []
    permutations' bs (x:xs) = (map (x:) $ permutations (bs ++ xs)) ++ (permutations' (x:bs) xs)

main = fmap (unlines . permutations) getLine >>= putStr

import sys

def func(lis):
	a,lis = lis[0],lis[1:]
	return ["".join([i,k]) for i in a for k in func(lis)] if lis else list(a)

if __name__ == "__main__":
	print func(sys.argv[1:])

import sys

def func(lis):
	return [ i+k for i in lis for k in func(lis.replace(i, ""))] if len(lis) > 1 else lis

if __name__ == "__main__":
	print func(sys.argv[1])

import Control.Monad

combinations = sequence . lines
main = putStr . unlines . combinations =<< getContents

insertions x [] = [[x]]
insertions x (y:ys) = (x:y:ys) : map (y:) (insertions x ys)

permutations [] = [[]]
permutations (x:xs) = concatMap (insertions x) (permutations xs)

main = putStr . unlines . permutations =<< getLine

splits xs = inits xs `zip` tails xs

permutations []     = [[]] 
permutations (x:xs) = [ps ++ x:qs | rs <- permutations xs, 
                                    (ps, qs) <- splits rs] 

splits []         = [([], [])] 
splits xxs@(x:xs) = ([], xxs):[(x:ps, qs) | (ps, qs) <- splits xs]

Combinations
#!/usr/bin/perl

while(<>) {
  chop;
  push @lines,$_;
}

&combine('',@lines);

sub combine {
  my $word = shift;
  if(0 == scalar(@_)) {
    print $word."\n";
    return;
  }
  my $line = shift;
  for my $l (split //,$line) {
    &combine($word.$l,@_);
  }
}

Permutations
#!/usr/bin/perl

$_ = <>;
chop;
my @word = split //,$_;

print STDERR "Permuting @word\n";

&perm('',@word);

sub perm {
  my $cur = shift;
  my @word = @_;

  if(0 == scalar(@word)) {
    print $cur."\n";
    return;
  }

  for(my $i = 0; $i <= $#word; $i++) {
    my $t = $word[$i];
    $word[$i] = $word[0];
    $word[0] = $t;

    &perm($cur.$word[0],@word[1..$#word]);

  }
}

#include <algorithm>
#include <string>
#include <iostream>

using namespace std;
int main()
{
  string word;
  cin >> word;
  sort(word.begin(), word.end());
  do
  {
    cout << word;
  }
  while(next_permutation(word.begin(), word.end());
}

mult cs vs = [ c:v | c<-cs, v<-vs ] -- для каждого символа и каждого вектора выполнить конкатенацию

combinations ws = foldr mult [[]] ws