1

我有这段java代码：

int maxDigit = 4;
for(int a = 0; a <= maxDigit; a++)
{
  for(int b = 0; b <= maxDigit; b++)
  {
    if(b != a){
      for(int c = 0; c <= maxDigit; c++)
      {
        if(c != a && c != b)
        {
          for(int d = 0; d <= maxDigit; d++)
          {
            if(d != a && d != b && d != c)
            {
              for(int e = 0; e <= maxDigit; e++)
              {
                if(e != a && e != b && e != c && e != d)
                {
                  String temp = a + "" + b + "" + c + "" + d + "" + e;
                  System.out.println(temp);
                  permutations.add(Integer.parseInt(temp));
                }
              }
            }
          }
        }
      }
    }
  }
}

如何将这段代码转换为函数？

目的是生成数字 0 到 9 的排列，在上面的代码中，它是从 0 到 4。将它放入函数中似乎很容易，但我无法立即找到它。

4

4 回答 4

4

这是获取字符串的所有排列的经典问题的变体。

你的教授希望你做出的归纳是这个问题很适合使用递归的解决方案。

字符串排列的基本算法s如下：

  1. 选择 中的第一项s。
  2. 获取其他项目的所有排列s（选定的项目除外）。
  3. 将所选项目添加到步骤 2 中的每个排列。
  4. 对 的下一个字符重复s。

这是使用函数式 Java库的有效解决方案。

导入这些...

import fj.F;
import fj.P2;
import fj.P1;
import fj.data.Stream;
import static fj.data.Stream.nil;
import static fj.data.Stream.cons;
import static fj.data.Stream.range;
import static fj.data.Enumerator.charEnumerator;
import static fj.data.Show.streamShow;
import static fj.data.Show.charShow;
import static fj.P2.map2_;

查找排列的递归函数：

public Stream<Stream<Character>> permutations(final Stream<Character> s) {
  return selections(s).bind(
    new F<P2<Character, Stream<Character>>, Stream<Stream<Character>>>() {
      public Stream<Stream<Character>>()
        f(final P2<Character, Stream<Character>> ys) {
          return permutations(ys._2()).bind(cons(ys._1()));
        }
      });
}

依次选择每个元素的递归函数：

public Stream<P2<Character, Stream<Character>>>
selections(final Stream<Character> s) {
  if (xs.isEmpty())
    return nil();
  else {
    final char x = xs.head();
    final Stream<Character> xs = s.tail()._1();
    return cons(P.p(x, xs),
      new P1<Stream<P2<Character, Stream<Character>>>>() {
        public Stream<P2<Character, Stream<Character>>> _1() { 
          return selections(xs).map(map2_().f(cons(x))));
        }
      });
  }
}

然后，获取字符 '0' 到 '9' 的所有排列：

Show<Stream<Character>> s = streamShow(charShow);
for (Stream<Character> ps : permutations(range(charEnumerator, '0', '9'))) {
  System.out.println(s.showS(ps));
}

编辑：这实际上是comonads的一个很好的用例。使用最新的函数式 Java 主干头，您可以使用 Zipper comonad 执行此操作，如下所示：

public static Stream<Stream<Character>> perms(Stream<Character> s) {
  Stream<Stream<Character>> r = single(Stream.<Character>nil());
  for (final Zipper<Character> z : fromStream(s))
    r = join(z.cobind(
      new F<Zipper<Character>, Stream<Stream<Character>>>() {
        public Stream<Stream<Character>> f(final Zipper<Character> zp) {
          return perms(zp.lefts().reverse().append(zp.rights())).map(compose(
            Stream.<Character>cons().f(zp.focus()),
              P.<Stream<Character>>p1()));
        }
      }).toStream());
  return r;
}
于 2009-04-06T21:16:18.033 回答
1

填补漏洞：

int[] indexes = { 0, 0, 0, 0, 0 };
addPermutations(maxDigit, indexes, 0, permutations);


void addPermutations(int max, int[] indexes, int currentIndex, List<Integer> permutations) {
    if (currentIndex == indexes.length) {
        // terminal case
        String temp = ...;
        System.out.println(temp);
        permutations.add(Integer.parseInt(temp));
    } else {
        // recursive case
        for (int i = 0; i <= max; i++) {
            if (... != i) {
                indexes[currentIndex] = i;
                addPermutations(max, indexes, currentIndex+1, permutations);
            }
        }
    }
}
于 2009-04-06T10:12:53.103 回答
0

没有代码，但算法应该如下。

假设您想要从 0 到 7 的 5 位数字的所有排列。为此：

  • 计算j =100000（1 + 5 个零）的 base-7 值的十进制值
  • Loop for i = 0; i < j; ++i，将每个转换i为 base-7 系统，可选地以零开头。
于 2009-04-06T10:15:52.287 回答
0

您可以使用 N 叉树，每个点有 4 个分支，递归地导航树并越过已经看到该节点数字的分支？

于 2009-04-06T10:41:43.957 回答