软件开发>杂文>2008


[返回]

 

Solve a permutation puzzle by computer program
一道趣题的几种解法

(Liu Xinyu) *

2009 1 12

18 使 方法

使C++Haskell 由于广指正 使LATEX2ɛFDL(GNU Free Documentation License) http://www.gnu.org/copyleft/fdl.html

Keywords: permutation, C++, Haskell

Corresponding Author:

1 Introduction

——《


PIC

 1: from www.zikai.org

样一 26 m 则这 a, b, c ... z m 5 a, b, c, d, e 5 样一

A B 各个

b a 的第AAfter), BBefore);c b 的第 A Bd c ……

并不AB ”ABA””acdb””cadb”等等

AB究竟 [1]

使解决 3 HaskellC++

2 method 1

2.1 permutation algorithms

举解 式时服方法 使 100 方法

AB AABBBA6,应英abcdefg7 7AABBBA 得到

使

 
filter hasPattern ” AABBBA ” permutation [a,b,c,d,e,f,g]

HaskellC++

 
std::string str= ” AABBBA ”; 
filter(hasPattern(str, permutation(str.length())));

abcdefg”AABBBA” 算他使解决的第 [2]

 
#include  <iostream>  
#include  <vector>  
#include  <algorithm>  
 
using namespace std; 
 
typedef vector<int>  NumberList; 
typedef vector< NumberList>  Result; 
 
void generate(Result&  res, const NumberList &  inst, int i, int n, int r){ 
  for(int j=1; j<= n;  ++j){ 
    if(find(inst.begin(), inst.end(), j) ==inst.end()){ 
      NumberList new_inst(inst); 
      new_inst.push_back(j); 
      if(i== r) 
        res.push_back(new_inst); 
      else 
        generate(res, new_inst, i+1, n, r); 
    } 
  } 
} 
 
Result permutation(int n, int r){ 
  Result res; 
  generate(res, NumberList(), 1, n, r); 
  return res; 
}

nr

  • i[1..n]j
  • j1i-1使使1ji
  • ir,r则找 i+1i+1

 
#include  <iterator>  
 
struct Print{ 
  void operator()(NumberList &  item){ 
    copy(item.begin(), item.end(), ostream_iterator<int>(cout, ” ”)); 
    cout<<\n”; 
  } 
}
 
int main(int, char**){ 
  Result res=permutation(5, 3); 
  for_each(res.begin(), res.end(), Print()); 
}

1 2 3  
1 2 4  
1 2 5  
...  
5 4 2  
5 4 3

由于C++ 的读[3]使

 
#include  <algorithm>  
 
int main(int, char**){ 
  string str(”abcdef”); 
   do{ 
    cout<<str<<\n”; 
  } 
  while(next_permutation(str.begin(), str.end())); 
}

并不nr false true

数式Haskell

 
import Data.List 
 
permutation []  =  [[]] 
permutation xs  =  [x:ys | x  <-  xs, ys  <-  permutation (delete x xs)]

使方法

permutation "abcd"  
["abcd","abdc","acbd",...,"dcab","dcba"]

list而非nr list

  • list
  • ={xysxlistys listx}

[1,2,3]x123, ys[2,3][1,3][1,2] xys

Haskell< -∈ xs xdeleteData.Listc

便Pnr

 
permutation xs n r=  if length xs  <=  n -
        then [[]] 
        else [x:ys | x  <-  xs, ys  <-  permutation (delete x xs) n r]

使方法

permutation "abcde" 5 3  
["abc","abd","abe",...,"edb","edc"]

2.2 pattern matching

ABC++式实 Haskell数式实

C++AB定的现先 得到

 
template< typename Compare >  
bool checkOrder(Compare op, char c, const string&  candidate){ 
  return op(candidate.find(c), candidate.find(c+1)); 
} 
 
bool hasPattern(string&  pattern, const string&  candidate){ 
  char c=’a’; 
  for(string::iterator it=pattern.begin(); it!=pattern.end();  ++it,  ++ c){ 
    if(*it==’ A’  &&  !checkOrder(less< char>(), c, candidate)) 
      return false; 
    if(*it==’ B’  &&  !checkOrder(greater< char>(), c, candidate)) 
      return false; 
  } 
  return true; 
}

hasPatternapattern读到Aab ab

hasPattern1

 
void enumStr(string pattern){ 
  string s; 
  for(int i=0; i<pattern.length()+1;++i) 
    s.push_back(’a’+i); 
  vector<string>  res; 
   do{ 
    if(hasPattern(pattern, s)) 
      res.push_back(s); 
  }while(next_permutation(s.begin(), s.end())); 
  for_each(res.begin(), res.end(), Print()); 
  cout<< ”total solution: ” <<res.size() <<\n”; 
} 
 
int main(int, char**){ 
  enumStr(” AAABBA ”); 
}

enumStrABpattern成初(abc...) STLhasPattern否符AB

使Printfunction object,码略

 
struct Print{ 
  template< typename Container>  
  void operator()(Container&  item){ 
    typedef typename Container::value_type value_type; 
    copy(item.begin(), item.end(), ostream_iterator<value_type>(cout, ” ”)); 
    cout<<\n”; 
  } 
};

a b c f e d g  
a b c f e g d  
a b c f g e d  
...  
f g a e b c d  
f g e a b c d  
total solution: 50

Haskell1 ’a’2’b’……26’z’

 
perm xs  =  permutation xs n n where n = length xs 
 
order f s  =  at s x ‘f‘ at s (1+x) where 
    x  =   minimum  s 
    at (y:ys) v  =  if v == y then 1 else 1  +  at ys v 
 
delete_min xs  =  filter (\x -> not (x == minimum  xs)) xs 
 
hasPattern [] _  =  True  
hasPattern (’A’:ps) s  =  order (<) s  &&  hasPattern ps (delete_min s) 
hasPattern (’B’:ps) s  =  order (>) s  &&  hasPattern ps (delete_min s)

hasPatternpattern pattern的第A patternB

数是order

数是delete_minfilter

 
enumStr1 pattern  =  filter f (perm [1..(1+length pattern)]) where 
    f  =  hasPattern pattern 
 
count1  =  length.enumStr1

enumStr1 "AAABBA"  
[[1,2,3,6,5,4,7],[1,2,3,6,5,7,4],[1,2,3,6,7,5,4],[1,2,6,3,5,4,7],  
[1,2,6,3,5,7,4],[1,2,6,3,7,5,4],[1,2,6,5,3,4,7],[1,2,6,5,3,7,4],  
[1,2,6,5,7,3,4],[1,2,6,7,3,5,4],[1,2,6,7,5,3,4],[1,6,2,3,5,4,7],  
[1,6,2,3,5,7,4],[1,6,2,3,7,5,4],[1,6,2,5,3,4,7],[1,6,2,5,3,7,4],  
[1,6,2,5,7,3,4],[1,6,2,7,3,5,4],[1,6,2,7,5,3,4],[1,6,5,2,3,7,4],  
[1,6,5,2,7,3,4],[1,6,5,7,2,3,4],[1,6,7,2,3,5,4],[1,6,7,2,5,3,4],  
[1,6,7,5,2,3,4],[6,1,2,3,5,4,7],[6,1,2,3,5,7,4],[6,1,2,3,7,5,4],  
[6,1,2,5,3,4,7],[6,1,2,5,3,7,4],[6,1,2,5,7,3,4],[6,1,2,7,3,5,4],  
[6,1,2,7,5,3,4],[6,1,5,2,3,4,7],[6,1,5,2,3,7,4],[6,1,5,2,7,3,4],  
[6,1,5,7,2,3,4],[6,1,7,2,3,5,4],[6,1,7,2,5,3,4],[6,1,7,5,2,3,4],  
[6,5,1,2,3,4,7],[6,5,1,2,3,7,4],[6,5,1,2,7,3,4],[6,5,1,7,2,3,4],  
[6,5,7,1,2,3,4],[6,7,1,2,3,5,4],[6,7,1,2,5,3,4],[6,7,1,5,2,3,4],  
[6,7,5,1,2,3,4]]  
 
count1 "AAABBA"  
50

算速

3 method 2

方法n n!hasPatternO(n2)

仍然AB nABn-1AB (b,c,...到第n+1),1AB Aab Ba b a

Haskell(C++ )

 
enumStrR from []  =  [[from]] 
 
enumStrR from (’A’:ps)  =  foldl (++) [] (map  f (enumStrR (from+1) ps)) where 
    f  =  insert_before from 
    insert_before y (x:xs)  =  if x == y+1  
        then [y:x:xs] 
        else [y:x:xs]++ (map  (x:) (insert_before y xs)) 
 
enumStrR from (’B’:ps)  =  foldl (++) [] (map  f (enumStrR (from+1) ps)) where 
    f  =  insert_after from 
    insert_after y (x:xs)  =  if x == y+1  
        then  map  (x:) (insert_any y xs) 
        else  map  (x:) (insert_after y xs) where 
            insert_any y []  =  [[y]] 
            insert_any y (x:xs)  =  [y:x:xs]++( map  (x:) (insert_any y xs)) 
 
enumStr2  =  enumStrR 1

enumStr2 = enumStrR 1 举具patternpattern”AAABBA”有英 enumStr2 ”AAABBA”1a 有英enumStrR 1 ”AAABBA”

pattern[[from]][[1]] pattern ABenumStrR (from+1) psa( from+1)b 应用mapinsert_afterinsert_beforeA insert_beforeinsert_after foldl合和++),

insert_before

 
insert_before y (x:xs)  =  if x == y+1  
    then [y:x:xs] 
    else [y:x:xs]++ (map  (x:) (insert_before y xs))

,( abcd就仅abcd), abcd)insert_before

insert_after

 
insert_after y (x:xs)  =  if x == y+1  
    then  map  (x:) (insert_any y xs) 
    else  map  (x:) (insert_after y xs) where 
        insert_any y []  =  [[y]] 
        insert_any y (x:xs)  =  [y:x:xs]++( map  (x:) (insert_any y xs))

insert_any成插 insert_any

count2 = length.enumStr2

方法过和方法1

EnumStr> enumStr2 "AAABBA"  
[[1,2,3,6,5,4,7],[1,2,6,3,5,4,7],[1,6,2,3,5,4,7],[6,1,2,3,5,4,7],  
[1,2,6,5,3,4,7],[1,6,2,5,3,4,7],[6,1,2,5,3,4,7],[1,6,5,2,3,4,7],  
[6,1,5,2,3,4,7],[6,5,1,2,3,4,7],[1,2,3,6,5,7,4],[1,2,6,3,5,7,4],  
[1,6,2,3,5,7,4],[6,1,2,3,5,7,4],[1,2,6,5,3,7,4],[1,6,2,5,3,7,4],  
[6,1,2,5,3,7,4],[1,6,5,2,3,7,4],[6,1,5,2,3,7,4],[6,5,1,2,3,7,4],  
[1,2,6,5,7,3,4],[1,6,2,5,7,3,4],[6,1,2,5,7,3,4],[1,6,5,2,7,3,4],  
[6,1,5,2,7,3,4],[6,5,1,2,7,3,4],[1,6,5,7,2,3,4],[6,1,5,7,2,3,4],  
[6,5,1,7,2,3,4],[6,5,7,1,2,3,4],[1,2,3,6,7,5,4],[1,2,6,3,7,5,4],  
[1,6,2,3,7,5,4],[6,1,2,3,7,5,4],[1,2,6,7,3,5,4],[1,6,2,7,3,5,4],  
[6,1,2,7,3,5,4],[1,6,7,2,3,5,4],[6,1,7,2,3,5,4],[6,7,1,2,3,5,4],  
[1,2,6,7,5,3,4],[1,6,2,7,5,3,4],[6,1,2,7,5,3,4],[1,6,7,2,5,3,4],  
[6,1,7,2,5,3,4],[6,7,1,2,5,3,4],[1,6,7,5,2,3,4],[6,1,7,5,2,3,4],  
[6,7,1,5,2,3,4],[6,7,5,1,2,3,4]]  
EnumStr> count2 "AAABBA"  
50  
EnumStr> count1 "AAB" == count2 "AAB"  
True  
EnumStr> count1 "AABB" == count2 "AABB"  
True  
EnumStr> count1 "AABBB" == count2 "AABBB"  
True  
EnumStr> count1 "A" == count2 "A"  
True  
EnumStr> count1 "AA" == count2 "AA"  
True  
EnumStr> count1 "ABA" == count2 "ABA"  
True

Haskell数式的递使C++ 的定使C++

 
typedef list<string>  ResultList; 
 
ResultList insertChar(string inst, char c){ 
  ResultList res; 
  typedef string::size_type size_type; 
  size_type pos =inst.find(*max_element(inst.begin(), inst.end())); 
  size_type from =  (c==’ A’)? pos+1 : 0; 
  size_type to   =  (c==’ A’)? inst.length() : pos; 
 
  for(size_type i= from; i<= to;  ++i){ 
    string s(inst); 
    s.insert(i, 1, char(inst[pos]+1)); 
    res.push_back(s); 
  } 
  return res; 
} 
 
ResultList enumStr2(string pattern){ 
  ResultList res; 
  res.push_back(string(”a”)); 
  for(string::iterator it=pattern.begin(); it!=pattern.end();  ++it){ 
    ResultList new_res; 
    for(list<string>::iterator inst=res.begin(); inst!=res.end();  ++inst){ 
      ResultList s=insertChar(*inst, *it); 
      copy(s.begin(), s.end(), 
           insert_iterator<ResultList>(new_res, new_res.end())); 
    } 
    res=new_res; 
  } 
  return res; 
}

enumStr2res表被 ”a”次从AB AB由于 insertCharcopy new_res使 AB

insertCharAB

的调方法

 
int main(int, char**){ 
  ResultList res= enumStr2(” AAABBA ”); 
  for_each(res.begin(), res.end(), Print()); 
  cout<< ”total solution:” <<res.size() <<\n”; 
}

f g e a b c d  
f e g a b c d  
f e a g b c d  
...  
a b c f e d g  
total solution:50

4 Method 3

方法度得到定的ABn : 1! + 2! + 3! + ... + n!

ABA abc...ABB ...cba

AABAA经决abcB dcd:

(1) a (2) b (3) c

d1,2,3AAA...AB(nA) BBB...BAn+1

AABBBde d3

(1): d在这ed(2): d 在这2(1) a (2) d b c(3): d在这3 (1) a (2) b (3) d c

iCi1 = i

       3  
 1,    2,    3

AABBB

        3  
 1,     2,     3  
 1,   1, 2   1,2,3

AABBBB

            3  
1,      2,               3  
1,   1,    2,     1,    2,     3  
1,   1,  1, 2    1,  1, 2  1,2,3

点的

AAABBA3A2B

       4  
1  2   3   4

5A, gf而放f C11 + C21 + C31 + C41 = 1 + 2 + 3 + 4(1)最左, (2)最左 2(3)最左23....

f最左C3+2+11 = 6g2 7;

f25g3到第7

...

AAABBA

                4  
1      2       3          4  
6    6 5     6 5 4     6 5 4 3

AAABBAA

                     4  
1           2                 3                      4  
6       6      5        6    5     4      6      5     4   3  
1..6  1..6    1..5    1..6 1..5  1..4    1..6  1..5  1..4 1..3

AA...(n1)...A BB...(n2)...B AA...(n3)...A ... BB...(np)...BAB n1+111n1+1 i1...in2 n3i(n1+n2+n3)-i+2..(n1+n2+n3+1)

方法便c++

 
template< typename Coll>  
void insertRange(int from, int to, Coll&  res){ 
  int step  =  from<to ? 1 : -1; 
  for(;;from +=step){ 
    res.push_back(from); 
    if(from == to) 
      break
  } 
} 
 
int enumStr3(string pattern){ 
  list<int>  res(1,1); 
  for(int i=0; i<pattern.length();  ++i){ 
    list<int>  new_res; 
    if(i  &&  pattern[i]!=pattern[i-1]) 
      for(list<int>::iterator node =res.begin(); node!=res.end();  ++ node) 
        insertRange(i+1, i-*node+2, new_res); 
    else 
      for(list<int>::iterator node =res.begin(); node!=res.end();  ++ node) 
        insertRange(1, *node, new_res); 
    res=new_res; 
  } 
  return accumulate(res.begin(), res.end(), 0); 
}

1ABAB else广 iinsertRange()1...iAB if步遍 iAB的当n, n-1, ... i

insertRange个辅是生fromto fromto以也使STLSGI iota()[4],[5].

的调

 
int main(){ 
    cout<< ”enum  AAABBA = ” << enumStr3(” AAABBA ”) <<\n”; 
}
enum AAABBA=50

Haskell

5 Other methods and Summary

他思Alecs King(alecs@perlchina.org)TopLanguage

 
get ab  =   sum  $ foldl f [1] ab 
    where f last ’A’  =  scanl (+) 0 last 
          f last ’B’  =  scanr (+) 0 last

者在 并不

AB0,小写 a

mABx1,x2,x3,...,xm+1 在这m+1m+1n1,n2,n3,...,nm+1 n1 + n2 + n3 + ... + nm+1 m+1ABmABX m+2

  • X = A 样一 21 数是n12n1 紧接3 2数是n23 n1 + n212... 0 + n1 + (n1 + n2) + (n1 + n2 + n3) + ... + (n1 + n2 + ... + nm+1)
  • X = B 样一 21 nm+12nm+1 紧接 (n1 + n2 + ... + nm+1) + (n1 + n2 + ... + nm) + ... + nm+1 + 0

Haskell

解决方法 方法 仍然方法 后还解决 并不意义 C++Haskell语用 由于必不批评

[1]   Top Language user group. http://groups.google.com/group/pongba/

[2]   , Feb. 2001

[3]   STL20026

[4]   http://www.sgi.com/tech/stl/

[5]   http://www.knowledgerush.com/kr/encyclopedia/APL_programming_language/

*Liu Xinyu
Ting Yu Xuan
5-2-201, ShiZiPo, Xi, DongZhiMenWai, DongCheng district, Beijing, 200027, P.R.China
Email: liuxinyu95@gmail.com
Tel: +86-1305-196-8666
Fax: N.A.