ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 实现自然数N的全排列

实现自然数N的全排列

原创 Linux操作系统 作者:yangtingkun 时间:2009-02-17 23:31:22 0 删除 编辑

今天同事问了一个问题,如何实现一个数N的全排列,也就是Pn。对于一个3来说,打印结果应该包括123132213231312321

 

 

当然还有一个小要求,不能使用递归算法。其实算法应该不复杂,不是递归就是循环。想了一下,觉得不难实现。

SQL其实最擅长这种类似笛卡儿的操作,下面是用SQL实现4个数的排列P4

SQL> WITH A AS (SELECT ROWNUM ID FROM DUAL CONNECT BY LEVEL <= 4)
  2  SELECT A.ID || B.ID || C.ID || D.ID
  3  FROM A, A B, A C, A D
  4  WHERE A.ID != B.ID
  5  AND A.ID != C.ID
  6  AND A.ID != D.ID
  7  AND B.ID != C.ID
  8  AND B.ID != D.ID
  9  AND C.ID != D.ID;

A.ID||B.ID||C.ID||D.ID
---------------------------------------------------------------------
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

已选择24行。

不过SQL实现固定值的排列结果和简单,但是如果输入参数是变量,那么SQL就没有办法写了,不过利用PL/SQLSQL的配合还是很容易实现的,代码如下:

SQL> CREATE OR REPLACE FUNCTION F_TEST (P_IN NUMBER) RETURN SYS_REFCURSOR AS
  2   V_STR VARCHAR2(32767);
  3   V_RETURN SYS_REFCURSOR;
  4  BEGIN
  5   V_STR := 'WITH A AS (SELECT ROWNUM ID FROM DUAL CONNECT BY LEVEL <= ' || P_IN || ') SELECT ';
  6   FOR I IN 1..P_IN LOOP
  7    V_STR := V_STR || 'A' || I || '.ID || ';
  8   END LOOP;
  9   V_STR := RTRIM(V_STR, '| ') || ' FROM ';
 10   FOR I IN 1..P_IN LOOP
 11    V_STR := V_STR || 'A A' || I || ', ';
 12   END LOOP;
 13   V_STR := RTRIM(V_STR, ', ') || ' WHERE ';
 14   FOR I IN 1..P_IN LOOP
 15    FOR J IN I+1..P_IN LOOP
 16     V_STR := V_STR || 'A' || I || '.ID != A' || J || '.ID AND ';
 17    END LOOP;
 18   END LOOP;
 19   OPEN V_RETURN FOR SUBSTR(V_STR, 1, LENGTH(V_STR) - 4);
 20   RETURN V_RETURN;
 21  END;
 22  /

函数已创建。

SQL> SELECT F_TEST(3) FROM DUAL;

F_TEST(3)
--------------------
CURSOR STATEMENT : 1

CURSOR STATEMENT : 1

A1.ID||A2.ID||A3.ID
--------------------------------------------------------------------------------------------
321
231
312
132
213
123

已选择6行。

当然,如果严谨一点,还应该对大于9和小于1的数进行输入判断,并对1进行单独的处理,不过不到30分钟的时间能实现到这样已经比较满意了。

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/4227/viewspace-553611/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 触发器迭代限制
请登录后发表评论 登录
全部评论
暂无介绍

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10471029