最近遇到一个算法问题,请各位大佬看看

正题

$array = [1,2,3,4,5,6,7,8];
$list = [
    [7,8,6,2,4],
    [7,1,2,3],
    [4,5,6,8],
    [6,7,8,1],
    [3,5,8]
];

说明: $list 里面的数据不固定,但是一定会包含 $array 里面的所有项。
结果: 需要得出类似于这种 :

$list = [
    0 => [7,8,6,2,4],
    1 => [1,3],
    2 => [5]
];
$list = [
    1 => [7,1,2,3],
    2 => [4,5,6,8]
];

去除原$list 里面各项的重复值,重新生成不重复的$list数据,使得新的$list既包含原有数据,又个项不重复。
需要计算出满足条件的所有结果出来。

解释

题目可以理解为,我要去买几样东西,每样东西只买一件。

$array = [1,2,3,4,5,6,7,8];        // 要买的东西的数组

然后,附近有几个超市, 每个超市都卖其中几样。

$list = [
    'a' => [7,8,6,2,4],
    'b' => [7,1,2,3],
    'c' => [4,5,6,8],
    'd' => [6,7,8,1],
    'e' => [3,5,8]
];        // 生成5个超市,每个超市只卖其中几种东西

问:我要买齐我所需要的东西,有多少种购买方式,分别是什么? 例如:

//举例其中一种购买方式
$list = [
    'a' => [7,8,6,2,4],        // 在a里买 7 8 6 2 4
    'b' => [1,3],            // 在b里买1 3
    'c' => [5]                // 在c里买 5
];
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
最佳答案
$array = [1,2,3,4,5,6,7,8];
$list = [
    'a' => [7,8,6,2,4],
    'b' => [7,1,2,3],
    'c' => [4,5,6,8],
    'd' => [6,7,8,1],
    'e' => [3,5,8]
];

$tmp = $tmp2 = $res = $res2 = [];
foreach($list as $shop=>$goods)
{
    foreach($goods as $name)
    {
        $tmp[$name][] = $shop;
    }
}
//保留需要的商品并调整顺序
foreach($array as $name)
{
    $tmp2[] = $tmp[$name];
}
//计算组合次数
function product($carry, $item)
{
    $carry *= count($item);
    return $carry;
}
$total = $num = array_reduce($tmp, 'product', 1);
//组合
foreach($tmp2 as $shop)
{
    $count = count($shop);
    $num /= $count;
    for($i = 0; $i < $total; ++$i)
    {
        $res[$i][] = $shop[intdiv($i, $num) % $count];
    }
}
//商品超市关系反转
foreach($res as $cur=>$select)
{
    foreach($select as $key=>$shop)
    {
        $res2[$cur][$shop][] = $array[$key];
    }
}
var_dump($res2);
2年前 评论
Yeardley (楼主) 2年前
讨论数量: 7

不是很明白这是个什么问题,描述太模糊了

2年前 评论
    function setList(&$array,&$list){
        if(empty($array)){
            return;
        }
        $rand = rand(1,count($array));
        $rand_keys = array_rand($array,$rand);
        $data = [];
        if(is_array($rand_keys)){
            foreach ($rand_keys as $key){
                $data[] = $array[$key];
            }
        }else{
            $data[] = $array[$rand_keys];
        }


        $list[] = $data;
        $array = array_diff($array,$data);
        sort($array);
        if(!empty($array)){
            $this->setList($array,$list);
        }
    }

$list = [];
$array = [1,2,3,4,5,6,7,8];
$this->setList($array,$list);
 dd($list);
2年前 评论
zhangwuphp (作者) 2年前
Yeardley (楼主) 2年前
function combination(array $options)
{
    $rows = [];

    foreach ($options as $option => $items) {
        if (count($rows) > 0) {
            // 2、将第一列作为模板
            $clone = $rows;

            // 3、置空当前列表,因为只有第一列的数据,组合是不完整的
            $rows = [];

            // 4、遍历当前列,追加到模板中,使模板中的组合变得完整
            foreach ($items as $item) {
                $tmp = $clone;
                foreach ($tmp as $index => $value) {
                    $value[$option] = $item;
                    $tmp[$index] = $value;
                }

                // 5、将完整的组合拼回原列表中
                $rows = array_merge($rows, $tmp);
            }
        } else {
            // 1、先计算出第一列
            foreach ($items as $item) {
                $rows[][$option] = $item;
            }
        }
    }

    return $rows;
}


$array = [1,2,3,4,5,6,7,8];
$list = [
    'a' => [7,8,6,2,4],
    'b' => [7,1,2,3],
    'c' => [4,5,6,8],
    'd' => [6,7,8,1],
    'e' => [3,5,8]
];

$haveList = [];
foreach ($array as $key => $value) {
    foreach ($list as $lk => $lv) {
        if(in_array($value, $lv)){
            $haveList[$value][] = $lk;
        }
    }
}

$haveList2 = combination($haveList);

$res = [];
foreach ($haveList2 as $key => $value) {
    $tmp = $tmp2 = $tmp3 =  [];
    foreach ($value as $key2 => $value2) {
        $tmp[$value2][] = $key2;
    }
    foreach ($tmp as $key3 => $value3) {
        foreach ($list[$key3] as $key4 => $value4) {
            if(in_array($value4, $value3)){
                $tmp2[$key3][] = $value4;
            }
        }
    }
    foreach (array_keys($list) as $key5 => $value5) {
        if(isset($tmp2[$value5])){
            $tmp3[$value5] = $tmp2[$value5];
        }
    }
    $mKey = md5(json_encode($tmp3));
    $res[$mKey] = $tmp3;
}
$res = array_values($res);
// echo count($res);die;
echo json_encode($res);
2年前 评论
Yeardley (楼主) 2年前
ilating (作者) 2年前
ilating (作者) 2年前
Yeardley (楼主) 2年前

瞎写

$array = [1,2,3,4,5,6,7,8];
$list = [
    [7,8,6,2,4],
    [7,1,2,3],
    [4,5,6,8],
    [6,7,8,1],
    [3,5,8]
];

$res = filter($list, $array);
var_dump($res);

function filter($list, $array)
{
    foreach($list as $k => $v)
    {
        foreach($v as $kk => $vv)
        {
            $idx = array_search($vv, $array);
            if(is_numeric($idx))
            {
                unset($array[$idx]);
            } else {
                unset($list[$k][$kk]);
            }
        }
    }
    return array_filter($list);
}
2年前 评论
Yeardley (楼主) 2年前


    public function test()
    {
        $array = [1, 2, 3, 4, 5, 6, 7, 8];        // 要买的东西的数组

        $lists = [
            'a' => [7, 8, 6, 2, 4],
            'b' => [7, 1, 2, 3],
            'c' => [4, 5, 6, 8],
            'd' => [6, 7, 8, 1],
            'e' => [3, 5, 8]
        ];
        $result = [];
        foreach ($array as $k=>$row) {
            $result[] = $this->sss($lists,$row);
        }
        $list = [];
        foreach ($result as $item){
            $list[$item['name']][] = $item['value'];
        }
        print_r($list);

    }


    public function sss($lists,$row)
    {
        foreach ($lists as $name=>$items) {
            $key = array_search($row, $items);
            if ($key !== false) {
                return ['name'=>$name,'value'=>$row];
            }
        }
    }
2年前 评论

按我的想法就是建立一个关联数组,商品=>超市的集合,然后每个商品选一个超市,排列组合就行了

2年前 评论
$array = [1,2,3,4,5,6,7,8];
$list = [
    'a' => [7,8,6,2,4],
    'b' => [7,1,2,3],
    'c' => [4,5,6,8],
    'd' => [6,7,8,1],
    'e' => [3,5,8]
];

$tmp = $tmp2 = $res = $res2 = [];
foreach($list as $shop=>$goods)
{
    foreach($goods as $name)
    {
        $tmp[$name][] = $shop;
    }
}
//保留需要的商品并调整顺序
foreach($array as $name)
{
    $tmp2[] = $tmp[$name];
}
//计算组合次数
function product($carry, $item)
{
    $carry *= count($item);
    return $carry;
}
$total = $num = array_reduce($tmp, 'product', 1);
//组合
foreach($tmp2 as $shop)
{
    $count = count($shop);
    $num /= $count;
    for($i = 0; $i < $total; ++$i)
    {
        $res[$i][] = $shop[intdiv($i, $num) % $count];
    }
}
//商品超市关系反转
foreach($res as $cur=>$select)
{
    foreach($select as $key=>$shop)
    {
        $res2[$cur][$shop][] = $array[$key];
    }
}
var_dump($res2);
2年前 评论
Yeardley (楼主) 2年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!