Получить непрерывное подмножество из заданных N чисел, используя меньше номеров цикла - PullRequest
Новая
       0

Получить непрерывное подмножество из заданных N чисел, используя меньше номеров цикла

0 голосов
/ 14 января 2020

Вот код: 

echo "<pre>";
function getContigousSubSet($n) 
{ 

    $set_array =  range(1,$n); 
    $main_array = array();
    for ($i=0; $i <$n; $i++) {  
         for($j = $i;$j < $n; $j++){  
          $interval_array = array();
          for ($k = $i; $k <= $j; $k++){
                array_push($interval_array,$set_array[$k]);
          }  array_push($main_array,$interval_array);
         }

    }
  return $main_array;
}

$result = getContigousSubSet(3);

var_dump($result);

Может ли сложность превратиться в O (n) с помощью каких-либо математических логик c или других способов?

Я ожидаю, что необходимо преобразовать этот код в одиночный для l oop, чтобы сложность могла быть O (n).

Если у кого-нибудь есть предложения в Python, то я тоже в порядке. Мне просто нужно увидеть, возможно ли это сделать или нет.

Существует способ получить числа возможных смежных подмножеств с помощью математической формулы.

(n⋅ (n + 1)) / 2

для ex A [] = [ 1,2,3] подмассивы: [1], [2], [3], [1,2], [2,3], [1,2,3]

(3 ⋅ (3 + 1)) / 2, то есть 6 непустых вложенных массивов

Ответы [ 2 ]

2 голосов
/ 14 января 2020

Вы не можете уменьшить сложность времени, поскольку хотите создать все подмассивы. Однако вы можете использовать функцию range в PHP, чтобы уменьшить количество вложенных циклов до 2. Обратите внимание, что это технически не уменьшает вложенную длину до 2, см. Код функции диапазона но код выглядит более идиоматически c. 

<?php

function getContigousSubSet($n){ 
    $result = array();
    for($i=1; $i<=$n;$i++){  
        for($j=$i;$j<=$n;++$j){
            $result[] = range($i,$j);
        }
    }
    return $result;
}

print_r(getContigousSubSet(10));

Демонстрация: https://3v4l.org/fZu5V

0 голосов
/ 14 января 2020

нет, нет способа сделать это. даже для печати вы должны использовать al oop 3 раза. но есть рекурсивный способ, который может сделать это быстрее, чем это.

вторая возможность - использовать его как логическое значение.

0 0 0 0 -> _ _ _ _ (пустое состояние)

0 0 0 1 -> _ _ _ A ({A})

.... и т. Д.

...