| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2423 人关注过本帖, 1 人收藏
标题:请教整行全排列问题
只看楼主 加入收藏
aaaaaa
Rank: 8Rank: 8
等 级:贵宾
威 望:21
帖 子:796
专家分:937
注 册:2012-9-4
收藏
得分:0 
我在做全排列的压力测试,寻找最快算法:
一些测试数据:
=Permutation(lnNum)  
P(8) = 40320组/21秒
P(9) = 362880组/949秒(15分钟
P(10) = 3628800组/21小时

不知道还可以提高吗?

民工子弟学校22班团小组长阳光模特队长冲锋篮球队前锋小苹果合唱队领唱蓝天舞蹈队编舞
2016-01-10 00:24
aaaaaa
Rank: 8Rank: 8
等 级:贵宾
威 望:21
帖 子:796
专家分:937
注 册:2012-9-4
收藏
得分:0 
如果把串联的 SQL-Select 语句拆开来变成并联的 SQL-Select 语句做,速度可以提升,现在的速度是:
=Permutation(lnNum)  
P(8) = 40320组/1.2秒
P(9) = 362880组/11秒
P(10) = 3628800组/113秒(2分钟-)

再试试看还可以提高吗?

民工子弟学校22班团小组长阳光模特队长冲锋篮球队前锋小苹果合唱队领唱蓝天舞蹈队编舞
2016-01-10 14:06
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43182
注 册:2014-5-20
收藏
得分:0 
用2楼的代码在小板机上试(CPU J1900, RAM 4G),好象差距不小,是否算法有问题?
图片附件: 游客没有浏览图片的权限,请 登录注册

2016-01-10 17:04
aaaaaa
Rank: 8Rank: 8
等 级:贵宾
威 望:21
帖 子:796
专家分:937
注 册:2012-9-4
收藏
得分:0 
我的机子:AMD CPU:1.4G,Ram:4G
如果不用 SQL-Select 语句的
用 4F 的递归法运算,
P(8,8) = 40320/1's,
P(9,9) = 362880/6's,
P(10,10) = 3628800/63's

估计纯代码递归法比 SQL-Select 语句快。

民工子弟学校22班团小组长阳光模特队长冲锋篮球队前锋小苹果合唱队领唱蓝天舞蹈队编舞
2016-01-10 17:40
aaaaaa
Rank: 8Rank: 8
等 级:贵宾
威 望:21
帖 子:796
专家分:937
注 册:2012-9-4
收藏
得分:0 
*!*    全排列 (SQL-Select 算法):

Clear
Set Talk Off
*!*    P(8,8) = 40320/2's, P(9,9) = 362880/11's, P(10,10) = 3628800/113's

? GenPermutation(10)

*!*    For I = 3 To 10
*!*        ?? I
*!*        ? GenPermutation( I )
*!*    Endfor


Function GenPermutation( pnSize )
    Local I, lnStart, lcItem, lcDestination
    lnStart = Seconds()

    Create Cursor TheResult ( Permutation c(pnSize) )
    Create Cursor ItemList ( Item C(1) )

    For i = 1 To pnSize
        Insert Into ItemList Values ( Chr( 65 + I - 1 ) )
    Endfor

    Select ItemList.Item + ItemListX.Item As Permutation ;
        from ItemList ;
        inner Join ItemList As ItemListX ;
        on ItemList.Item != ItemListX.Item ;
        into Cursor temp2

    Select TheResult
    Append From Dbf( "temp2" )

    For I = 3 To pnSize
        Create Cursor StepPermutation ( Permutation c(pnSize) )
        Select ItemList
        Scan
            lcItem = ItemList.Item
            Select lcItem + Permutation As Permutation ;
                from TheResult ;
                into Cursor Temp2 nofilter ;
                where ! ( lcItem $ Permutation )

            Select StepPermutation
            Append From Dbf( "Temp2" )
        Endscan

        If I < pnSize
            Select TheResult
            Zap
            Append From Dbf( "StepPermutation" )
        Else
            Select * ;
                from StepPermutation ;
                into Cursor TheResult
        Endif
    Endfor

    Use In ItemList
    Use In Temp2
    Use In StepPermutation

    Select TheResult

    Return "P(" + Transform( pnSize ) + ") = " + Transform( Reccount() ) + " 组" + Chr(13) + Chr(10) + ;
        "耗时 = " + Transform( Seconds() - lnStart, "99,999.99" ) + " 秒" + Chr(10)
Endfunc

民工子弟学校22班团小组长阳光模特队长冲锋篮球队前锋小苹果合唱队领唱蓝天舞蹈队编舞
2016-01-10 17:59
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43182
注 册:2014-5-20
收藏
得分:0 
换位法全排序
速度还是比用 SELECT - SQL 慢小小

程序代码:
n = 9
DIMENSION aNi[n]
sCmd = ""
FOR i = 1 TO n 
    aNi[i] = i
    sCmd = sCmd + ",列" + TRANSFORM(i) + " I"
ENDFOR
sCmd = "CREATE CURSOR tt (" + SUBSTR(sCmd, 2) + ")"
EXECSCRIPT(sCmd)
tt = DATETIME()
DO WHILE !myNext()
ENDDO
GO top
BROWSE NOWAIT
MESSAGEBOX(TRANSFORM(n)+"个数的全排列共 " + TRANSFORM(RECCOUNT()) + " 种 " + TRANSFORM(DATETIME()-tt)+ "秒")
RETURN

FUNCTION myNext()
    LOCAL i, j, n, tmp
    n = ALEN(aNi)
    APPEND FROM ARRAY aNi
    FOR i = n TO 2 STEP -1
        IF aNi[i] > aNi[i-1]
            EXIT
        ENDIF
    ENDFOR
    IF i < 2
        RETURN .T.
    ENDIF
    FOR j = n TO i STEP -1
        IF aNi[j] > aNi[i-1]
            tmp = aNi[i-1]  
            aNi[i-1] = aNi[j]
            aNi[j] = tmp
            EXIT
        ENDIF
    ENDFOR
    FOR j = i TO (i + n)/2
        tmp = aNi[j]
        aNi[j] = aNi[i + n - j]
        aNi[i + n - j] = tmp
    ENDFOR
    RETURN .F.          
ENDFUNC
2016-01-11 15:51
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43182
注 册:2014-5-20
收藏
得分:0 
回复 16楼 吹水佬
试了一下,原来 APPEND FROM ARRAY aNi 这句占了约一半时间,看来算法速度还可以,只是输出结果有点耗费,能提高输出速度还是不错的。
2016-01-13 09:36
快速回复:请教整行全排列问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.033466 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved