OU - 极湖 - Posts tagged by "".

Posts tagged with "算法"

单循环赛程算法

Monday, 11. February 2008, 04:17:42

从这儿看到题目，翻译如下：

任意偶数个队，进行单循环赛，须在最短日期之内举行完全部赛事，请作出日程表之一。
（补充：每个队每天只能举行一场比赛）

并非只有一解的情况也有。
如果有余力，请给出所有可能的答案。

这属于体育赛事日程安排的问题，在数学上，比较接近“柯克曼女生问题”。

例如，4个队的情况下

1-2 3-4
1-3 2-4
1-4 2-3

６个队的情况下

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

是其一解。

这个问题看起来简单，做起来却颇伤脑筋。
我在网上找了一个比较容易理解的算法，就是一个队不动，其它队组成一个“环”之后旋转，每转一次得到一天的赛程。

用 JavaScript 实现的程序如下：

/**
 * 旋转数组
 */
function rotateArray(aOld) {
    var iLast = aOld.length - 1;
    return [aOld[iLast]].concat(aOld.slice(0, iLast));
}

/**
 * 生成日程表
 */
function getLeageSchedule(aTeam) {
    var aResult = [];
    if(aTeam.length%2 != 0) {
        aTeam.push('');
    }
    var vFirst = aTeam[0];
    var aCycle = aTeam.slice(1);
    var iHalfLen = aTeam.length/2;
    for(var i=0; i<aCycle.length; i++) {
        var aLeft = [vFirst].concat(aCycle.slice(iHalfLen).reverse());
        var aRight = aCycle.slice(0, iHalfLen);
        var aGames = [];
        for(var j=0; j<aLeft.length; j++) {
            if(aLeft[j] != '' && aRight[j] != '') {
                aGames.push(aLeft[j] + '-' + aRight[j]);
            }
        }
        aResult.push(aGames);
        aCycle = rotateArray(aCycle);
    }
    return aResult;
}

//测试
var aTeam = [1,2,3,4,5,6];
var aSchedule = getLeageSchedule(aTeam);
for(var i=0; i<aSchedule.length; i++) {
    document.write(aSchedule[i].join('  ') + '
');
}

程序运行的结果如下：
1-2 6-3 5-4
1-6 5-2 4-3
1-5 4-6 3-2
1-4 3-5 2-6
1-3 2-4 6-5

这个算法可能不是太好，只不过比较简单，有一点自己的发挥就是还考虑了奇数队的情况。
问题后面有人用 Ruby 实现了这一算法，总共才8行，实在让人佩服。

No comments

最简单的全排列算法

Tuesday, 25. December 2007, 07:45:52

JavaScript, 算法, 排列

刚开始接触排列组合算法的时候，觉得很复杂，越想越难，有了想法，程序写完运行结果还总不正确。一旦成功，发现，原来解决的方法竟然如此简单！

今天实现了一个新的排列算法，原理如下：

为方便说明，要进行排序的数组假设是[0,1,2]

先取数组的第一个元素，作成数组，结果是
[0]

接下来取数组的第二个元素，按顺序插入以上数组的"空位"，结果是
[0,1]
[1,0]

继续取数组的第三个元素，按顺序插入以上每一数组的"空位"，结果是
[2,0,1]
[0,2,1]
[0,1,2]
[2,1,0]
[1,2,0]
[1,0,2]

这，不就是原数组的全排列？

怎么样，简单吧？
还有比这个更简单的排列算法吗？如果有，请告知，多谢！

源代码如下：

<script type="text/javascript">
/**
 * 数组克隆（复制）
 * @return 数组的拷贝
 */
Array.prototype.clone = function () {
    return this.concat();
};

/**
 * 插入数组元素(值)到指定位置
 * @param iIndex 指定位置(索引)
 * @param vItem 欲插入的元素(值)
 */
Array.prototype.insertAt = function (iIndex, vItem) {
    this.splice(iIndex, 0, vItem);
    return this;
};

/**
 * 插入递归全排列算法
 */
function getAllOrderByInsert(aData, aOrder) {
    if(!aOrder) {
        aOrder = [[aData[0]]];
    }
    var iLen = aOrder[0].length;
    if(iLen == aData.length) {
        return aOrder;
    }
    var aNewOrder = [];
    var vInsert = aData[iLen];
    for(var i = 0; i < aOrder.length; i++) {
        var aOld = aOrder[i];
        for(var j = 0; j <= aOrder[i].length; j++) {
            var aNew = aOld.clone().insertAt(j, vInsert);
            aNewOrder.push(aNew);
        }
    }
    return getAllOrderByInsert(aData, aNewOrder);
}

//测试
var aData = [0,1,2,3,4];
document.write("
数组[" + aData.join(" ") + "]的全排列:
"); 

var aOut = getAllOrderByInsert(aData);
for(var i=0; i<aOut.length; i++) {
    document.write(aOut[i].join(" ") + "
"); 
}
</script>

用于测试的HTML文件
easy_order.html

No comments

二十四点

Thursday, 20. December 2007, 10:35:35

jQuery, 游戏, 算法, 数学 ...

这些天研究排列组合的算法，是为了做一个“二十四点”的小程序。
经过几天努力，总算做出了可以自动取得正确算式的程序，就在此发表一下。

程序截图如下：

网址1：
http://staticlake.appspot.com/point24/index.html
网址2：
http://geelake.com/point24/

因为用JavaScript做程序，还是借用了jQuery，如果您对程序本身感兴趣，可以自己查看网页代码。

技术要点：
数组操作技巧
排列组合算法
正则表达式
网页元素拖放处理

从今往后,不论你身在何地，如果有人考你24点的算式，只需打开这个网页，答案很快就有啦。

No comments

可重复组合算法的JavaScript实现

Wednesday, 19. December 2007, 01:09:57

函数, 算法, 排列组合, JavaScript

上一篇《粗浅的排列组合算法之 JavaScript 实现》，其中的组合算法得到的是不重复组合，比如，从[a, b, c]中取2元素的组合，结果是：

a b
a c
b c

而有时候,需要得到下面这样可重复的组合:

a a
b a
c a
a b
b b
c b
a c
b c
c c

这时候就不能用先前的算法了，为此作了一个新的算法，简单说明如下：

首先，取组合顺序的最小索引数组合最大索引数组，比如，4取2组合的最小和最大索引数组分别是：

[0,0]  [3,3]

接下来，就是怎么得到中间数组的问题了，这时候，很自然就能想到 n 进制的方法。
从最小索引数组开始，先在第 0 位加 1，加到最大值就进 1，直到所有的位都是最大值。
索引数组得到了，组合也就有了。

代码如下：

<script type="text/javascript">
/**
 * 按索引数组取得其中一部分
 */
Array.prototype.getPart = function ( aIndex ) {
    var aPart = [];
    for (var i=0; i < aIndex.length; i++) {
        aPart.push(this[aIndex[i]]);
    }
    return aPart;
};

/**
 * 取得可重复组合的下一个顺序数组(n进制算法)
 */
function getNextIndexArray(aIndex, max) {
    for(var i = 0; i < aIndex.length; i++) {
        if(aIndex[i] < max) {
            aIndex[i] += 1;
            return aIndex;
        } else {
            for(var j = i+1; j < aIndex.length; j++) {
                if(aIndex[j] < max) {
                    aIndex[j] += 1; 
                    for(var k=j-1; k>=0; k--) {
                        aIndex[k] = 0; 
                    }
                    return aIndex;
                }
            }
        }
    }
    return null;
}

/**
 * 从数组中生成指定长度的可重复组合(aaa,bbb,aab ...)
 */
function combInArrayDup(aData, n) {
    var aResult = [];

    var aIndex = [];
    for(var i = 0; i < n; i++) {
        aIndex[i] = 0;
    }
    var iMax = aData.length - 1;
    for(;;) {
        if(aIndex == null) {
            break;
        }
        aResult.push(aData.getPart(aIndex));
        aIndex = getNextIndexArray(aIndex, iMax);
    }
    return aResult;
}
</script>

测试

var aData = [1,2,3,4];
document.write("
数组[" + aData.join(" ") + "]的2元素可重复组合:
"); 
var aOut = combInArrayDup(aData, 2);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

用于测试的HTML文件
plzhfunc2.html

No comments

粗浅的排列组合算法之 JavaScript 实现

Friday, 14. December 2007, 08:28:29

算法, 组合, 排列, JavaScript ...

东拼西凑加修改，做了几个函数，用于实现排列组合。函数如下：

/**
 * 克隆数组
 */
Array.prototype.clone = function () {
    return this.concat();
};

/**
 * 按指定的顺序数组重新排列
 */
Array.prototype.reOrder = function ( aOrder ) {
    var aClone = this.clone();
    for (var i=0; i < aOrder.length; i++) {
        this[aOrder[i]] = aClone[i];
    }
    return this;
};

/**
 * 取得 0 到 iLen 的所有排列顺序
 */
function getOrders( iLen ) {
    var aResult = [];
    var aNum = [];
    var aNumFlag = [];
    var i, j;
    for(i = 0; i < iLen; i++) {
        aNum[i] = i,
        aNumFlag[i] = 1;
    }
    
    for(;;){
        aResult.push(aNum.clone());
        aNumFlag[aNum[iLen-1]] = 0;
        for(i = iLen - 2; i>=0; i--){
            aNumFlag[aNum[i]] = 0;
            if(aNum[i] < aNum[i+1]) {
                break;
            }
        }
        if( i < 0) {
            break;
        }

        for(j = aNum[i] + 1; j < iLen; j++){
            if(!aNumFlag[j]) {
                break;
            }
        }

        aNumFlag[j] = 1;
        aNum[i] = j;
        for(j=0, i++; i < iLen; j++) {
            if(!aNumFlag[j]) {
                aNum[i++] = j;
                aNumFlag[j] = 1;
            }
        }
    }
    return aResult;
}

/**
 * 生成数组的全排列
 * 方法: 先生成数组长度以下的所有顺序, 然后根据顺序数组重排原数组
 */
function arrayInAllOrder( aData ) { 
    var aResult = []; 
    var aOrders = getOrders(aData.length);
    var aOrder = aOrders.shift();
    while(aOrder) {
        aResult.push(aData.clone().reOrder(aOrder));
        aOrder = aOrders.shift();
    }
    return aResult;
}

/**
 * 得到从 m 元素中取 n 元素的所有组合
 * 结果为[0,1...]形式的数组, 1表示选中，0表示不选
 */
function getCombFlags(m, n) {
    if(n == null || n < 1) {
        return [];
    }

    var aResult = [];
    var aFlag = [];
    for (i=0; i<m; i++) {
        aFlag[i] = (i < n) ? 1 : 0;
    }

    aResult.push(aFlag.clone());
    var bNext = true;
    while (bNext) {
        var iCnt1 = 0;
        for (var i = 0; i < m - 1; i++) {
            if (aFlag[i] == 1) {
                if(aFlag[i+1] == 0) {
                    for(j = 0; j < i; j++) {
                        aFlag[j] =  (j < iCnt1) ? 1 : 0;
                    }
                    aFlag[i] = 0;
                    aFlag[i+1] = 1;
                    var aTmp = aFlag.clone();
                    aResult.push(aTmp);
                    if(aTmp.slice(-n).join("").indexOf('0') == -1) {
                        bNext = false;
                    }
                    break;
                }
                iCnt1++;
            }
        }
    }
    return aResult;
} 

/**
 * 从数组中生成指定长度的组合
 * 方法: 先生成[0,1...]形式的数组, 然后根据0,1从原数组取元素，得到组合数组
 */
function combInArray( aData, n) {
    var aResult = [];
    if(n > aData.length) {
        return aResult;
    }
    
    var aaFlags = getCombFlags(aData.length, n);
    var aFlag = aaFlags.shift();
    while(aFlag) {
        var aComb = [];
        for(var i = 0; i < aData.length; i++) {
            if(aFlag[i]) {
                aComb.push(aData[i]);
            }
        }
        aResult.push(aComb);
        aFlag = aaFlags.shift();
    }
    
    
    return aResult;
}

测试一

document.write("3以下的所有排列顺序:
"); 
var aOut = getOrders(3);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(","),"
"); 
}

测试二

var aData = ['a','b','c','d'];
document.write("
数组[" + aData.join(" ") + "]的排列:
"); 
var aOut = arrayInAllOrder(aData);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

测试三

document.write("
5取3标志位数组:
"); 
var aOut = getCombFlags(5, 3);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

测试四

var aData = ['a','b','c','d','e'];
document.write("
数组[" + aData.join(" ") + "]的3元素组合:
"); 
var aOut = combInArray(aData, 3);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

用于测试的HTML文件
plzhfunc.html

【补充】
可重复组合算法的JavaScript实现
最简单的全排列算法

No comments

PHP: 二维数组按指定列排序

Wednesday, 14. November 2007, 08:27:14

排序, 算法, PHP

<?php
/**
 * 
 * 二维数组按指定列排序
 * @param     $arr_data     原数组
 * @param     $field     指定列
 * @param     $descending    是否降顺（默认升顺）
 * @return    排列好的数组
**/
function ARRAY_sort_by_field($arr_data, $field, $descending = false)
{
    $arrSort = array();
    foreach ( $arr_data as $key => $value ) {
        $arrSort[$key] = $value[$field];
    }

    if( $descending ) {
        arsort($arrSort);
    } else {
        asort($arrSort);
    }

    $resultArr = array();
    foreach ($arrSort as $key => $value ) {
        $resultArr[$key] = $arr_data[$key];
    }

    return $resultArr;
}

//测试：
$arr = array (
array ('s' => 'aaa', 'i' => 3),
array ('s' => 'bbb', 'i' => 2),
array ('s' => 'ccc', 'i' => 4),
array ('s' => 'ddd', 'i' => 1),
);

print_r(ARRAY_sort_by_field($arr, 'i'));
print_r(ARRAY_sort_by_field($arr, 'i', true));
?>

No comments