如何从一组数字中形成最大数字

Question

给定一组数字，我需要以产生最大值的方式排列它们。

例如，如果给定的数字是{3,1,13,34,8}，则排列8343131给出最大值。如果给定的数字是{1,34,3,98,9,66,45,4}，则排列998764543431给出最大值。

$array = array("3", "1", "13", "34", "8");

需要有输出如下

OUTPUT:
8343131

使用PHP我该如何实现？

Answer 1

给定数组值的Find all possible combination并找到最大值

function permute($arg) {
    $array = is_string($arg) ? str_split($arg) : $arg;
    if(1 === count($array))
        return $array;
    $result = array();
    foreach($array as $key => $item)
        foreach(permute(array_diff_key($array, array($key => $item))) as $p)
            $result[] = $item . $p;
    return $result;
}

$array = array("3", "1", "13", "34", "8");

echo max(permute($array));

现场演示：https://eval.in/920239

输出为：8343131

Answer 2

我假设你想要的是使用数组中字符串的数字创建最大可能的数字。

实现此目的的最简单方法是创建一个包含所有数字的数组，并从最高到最低排序，然后使用这些数字创建一个数字：

$array = array("3", "1", "13", "34", "8");

$tmp = array();
foreach ($array as $i)
    $tmp = array_merge($tmp, str_split($i, 1));

rsort($tmp, SORT_NUMERIC);

$maxNumber = implode('', $tmp);

这将输出8433311，这是所提供字符串数字的最大数字。

Answer 3

不需要检查所有排列。我认为这可以在O（k.n.log（n））时间内解决，其中n是数组大小，k是最长字符串中的字符数。

我们的想法是首先通过填充字符串来对字符串进行排序，这样所有字符串都具有相同的长度。填充应该通过在必要时多次重复原始字符串然后剪切到公共长度来实现。当该长度被认为是最大字符串的双倍长度时，结果将是正常的。

以此输入为例：

["1", "1112", "11121", "111230", "385", "38530"]

然后算法将扩展这些字符串如下：

["111111111111","111211121112","111211112111","111230111230","385385385385","385303853038"]

按降序排序，这给出：

["385385385385","385303853038","111230111230","111211121112","111211112111","111111111111"]

转换回原始值：

["385", "38530", "111230", "1112", "11121", "1"]

结果如下：

"385385301112301112111211"

这是代码：

$array = ["1", "1112", "11121", "111230", "385", "38530"];
$maxlen = 2 * max(array_map('strlen', $array));
$padded = array_map(function ($a) use ($maxlen) {
    return substr(str_repeat($a, ceil($maxlen / strlen($a))), 0, $maxlen);
}, $array);
array_multisort($padded, SORT_DESC, $array);
$result = implode("", $array);

echo $result;

与接受的答案不同，对于具有多个值的数组，这也适用于合理的时间：

看它在eval.in上运行输入：

["3", "1", "7", "8", "9", "2", "4", "6", "5", "0", "15", "29", "32", "41", 
 "551", "56", "671", "6713", "782", "7820", "88", "880", "91", "9121"] 

它输出：

991912188888078278207671671365655514413322921510