PHP

Question

我有一个二维数组。假设每个 pos 职位我有一个 os 候选人来填补它。

例如：

Position 0 -> Candidates: 1,2,3
Position 1 -> Candidates: 3,4,5
Position 2 -> Candidates: 4,5

翻译：

Array_Position(
  array('1', '2', '3'),
  array('3', '4','5'),
  array('4', '5')   
);

我想要所有组合，有 2 个限制：

没有重复（如果候选人已经在一个 pos 中，它不能再次出现在另一个 pos 中）。
这不可能发生：
1-4-4
3-3-4
候选人不能 "smaller" 比他的前任。
这不可能发生：
1-5-4
3-5-4

在这种特殊情况下，所有 possible 组合将是：
1-3-4
1-3-5
1-4-5
2-3-4
2-3-5
2-4-5
3-4-5

我看到了一些这样的回答：

<?php       
    function array_cartesian() {
        $_ = func_get_args();
        if(count($_) == 0)
            return array(array());
        $a = array_shift($_);
        $c = call_user_func_array(__FUNCTION__, $_);
        $r = array();
        foreach($a as $v)
            foreach($c as $p)
                $r[] = array_merge(array($v), $p);
        return $r;
    }

    $cross = array_cartesian(
        array('1', '2', '3'),
        array('3', '4','5'),
        array('4', '5') 
    );

    print_r($cross);

?>

但其中 none 解决了 2 个限制。

有什么帮助吗？

谢谢！

Answer 1

由于任何候选人都不能小于他的前任，因此链中的任何位置都不能重复。以下代码可以解决问题，检查它是否适合您。

<?php

function permute()
{
    $result = array();

    if (func_num_args() == 0)
        return $result; // empty array

    foreach (func_get_arg(0) as $value)
        nextPermute($result, $value, $value, 1, func_get_args());

    return $result;
}

function nextPermute(&$result_array, $permute_value,
                    $last_value, $next_arg, $all_args)
{
    if ($next_arg < count($all_args))
    {
        foreach ($all_args[$next_arg] as $value)
            if ($value > $last_value)
                nextPermute($result_array, $permute_value . '-' . $value, $value, $next_arg + 1, $all_args);
    }
    else
        array_push($result_array, $permute_value);
}

$cross = permute(
    array('1', '2', '3'),
    array('3', '4', '5'),
    array('4', '5')
);

print_r($cross);

?>

PHP - 二维数组中的所有排列 - 唯一且有序的值

PHP - All permutations in a 2D array - Unique and ordered values

arrays

combinations

permutation