PHP associative arrays를 이용한 데카르트 제품 찾기

다음과 같은 배열이 있다고 가정 해보십시오.

Array
(
    [arm] => Array
        (
            [0] => A
            [1] => B
            [2] => C
        )
    [gender] => Array
        (
            [0] => Female
            [1] => Male
        )
    [location] => Array
        (
            [0] => Vancouver
            [1] => Calgary
        )
)

어떻게 외부 연관 배열의 키를 보존하고 내부 연관 배열에서 키를 사용하면서 데카르트 곱을 찾을 수 있습니까? 알고리즘의 결과는 다음과 같아야합니다.

Array
(
    [0] => Array
        (
            [arm] => A
            [gender] => Female
            [location] => Vancouver
        )

    [1] => Array
        (
            [arm] => A
            [gender] => Female
            [location] => Calgary
        )

    [2] => Array
        (
            [arm] => A
            [gender] => Male
            [location] => Vancouver
        )

...etc.

꽤 많은 수의 데카르트 생성 알고리즘을 살펴 보았지만 연관 키를 보존하는 방법에 대해 자세히 설명하지 않습니다. 현재 사용하고있는 알고리즘은 숫자 인덱스 만 제공합니다.

    $result = array();
    foreach ($map as $a) {
        if (empty($result)) {
            $result = $a;
            continue;
        }
        $res = array();
        foreach ($result as $r) {
            foreach ($a as $v) {
                $res[] = array_merge((array)$r, (array)$v);
            }
        }
        $result = $res;
    }

    print_r($result);

어떤 도움을 주시면 감사하겠습니다.

해결법

==============================

1.여기에 내가 부끄러워하지 않을 해결책이 있습니다.

여기에 내가 부끄러워하지 않을 해결책이 있습니다.

예제에서와 같이 N 개의 하위 배열로 입력 배열 $ input이 있다고 가정합니다. 마다 하위 배열에는 Cn 항목이 있습니다. 여기서 n은 $ input 내부의 색인이고 키는 Kn입니다. 나는 n 번째 서브 - 어레이의 i 번째 항목을 Vn으로 언급 할 것이다.

아래 알고리즘은 유도에 의해 버그가없는 것으로 증명 될 수 있습니다.

1) N = 1 일 때 데카르트 곱은 단순히 배열 (0 => 배열 (K1 => V1,1), 1 => 배열 (K1 => V1,2), ...) . 이것은 간단한 foreach로 할 수 있습니다.

2) $ result가 이미 첫 번째 N-1 하위 배열의 데카르트 곱을 가지고 있다고 가정합니다. $ result와 N 번째 서브 - 배열의 데카르트 곱은 다음과 같이 생성 될 수 있습니다 :

3) $ 제품 안에있는 각 항목 (h 열)에 KN => VN, 1 값을 추가하십시오. 결과 항목 (값이 추가됨)을 기억하십시오. 나는 그것을 $ item이라고 부를 것이다.

4a) $ product 내부의 각 배열에 대해 :

4b) 집합 VN, 2 ... VN, CN의 각 값에 대해 $ item의 사본을 $ product에 추가하지만 키 KN을 사용하여 값을 VN, m으로 변경합니다 (모두 2 <= m <= CN ).

두 번의 iteration 4a ($ product에 대해)와 4b (N 번째 input sub-array에 대한)는 $ 반복 결과 앞에 CN 항목이있는 결과로 끝납니다. 결국 $ 결과는 실제로 첫 번째 N 개의 하위 배열.

따라서 알고리즘은 모든 N에서 작동합니다.

이것은 있어야했던 것보다 쓰기가 더 어려웠습니다. 제 공식적인 증거가 확실히 녹슬고 있습니다 ...

function cartesian($input) {
    $result = array();

    while (list($key, $values) = each($input)) {
        // If a sub-array is empty, it doesn't affect the cartesian product
        if (empty($values)) {
            continue;
        }

        // Seeding the product array with the values from the first sub-array
        if (empty($result)) {
            foreach($values as $value) {
                $result[] = array($key => $value);
            }
        }
        else {
            // Second and subsequent input sub-arrays work like this:
            //   1. In each existing array inside $product, add an item with
            //      key == $key and value == first item in input sub-array
            //   2. Then, for each remaining item in current input sub-array,
            //      add a copy of each existing array inside $product with
            //      key == $key and value == first item of input sub-array

            // Store all items to be added to $product here; adding them
            // inside the foreach will result in an infinite loop
            $append = array();

            foreach($result as &$product) {
                // Do step 1 above. array_shift is not the most efficient, but
                // it allows us to iterate over the rest of the items with a
                // simple foreach, making the code short and easy to read.
                $product[$key] = array_shift($values);

                // $product is by reference (that's why the key we added above
                // will appear in the end result), so make a copy of it here
                $copy = $product;

                // Do step 2 above.
                foreach($values as $item) {
                    $copy[$key] = $item;
                    $append[] = $copy;
                }

                // Undo the side effecst of array_shift
                array_unshift($values, $product[$key]);
            }

            // Out of the foreach, we can add to $results now
            $result = array_merge($result, $append);
        }
    }

    return $result;
}

$input = array(
    'arm' => array('A', 'B', 'C'),
    'gender' => array('Female', 'Male'),
    'location' => array('Vancouver', 'Calgary'),
);

print_r(cartesian($input));

==============================
2.다음은 @ Jon의 직교 함수 최적화 된 버전입니다.

다음은 @ Jon의 직교 함수 최적화 된 버전입니다.
```
function cartesian($input) {
    $result = array(array());

    foreach ($input as $key => $values) {
        $append = array();

        foreach($result as $product) {
            foreach($values as $item) {
                $product[$key] = $item;
                $append[] = $product;
            }
        }

        $result = $append;
    }

    return $result;
}
```
이 알고리즘의 수학에 대한 자세한 내용은 다음을 참조하십시오. http://en.wikipedia.org/wiki/Cartesian_product

이 알고리즘에 대한 다른 예제를 다른 언어로보기 : https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists

==============================

3.여기에 내가 생각해 낼 수있는 것이있다.

여기에 내가 생각해 낼 수있는 것이있다.

function inject($elem, $array) {
    return array_map(function ($n) use ($elem) { return array_merge((array)$elem, (array)$n); }, $array);
}

function zip($array1, $array2) {
    return array_reduce($array1, function ($v, $n) use ($array2) { return array_merge($v, inject($n, $array2));  }, array());
}

function cartesian_product($array) {
    $keys = array_keys($array);
    $prod = array_shift($array);
    $prod = array_reduce($array, 'zip', $prod);
    return array_map(function ($n) use ($keys) { return array_combine($keys, $n); }, $prod);
}

(PHP는 그러한 것들에 대해 너무 장황하기 때문에 의사 배열 /리스트 / 사전 표기법을 사용하십시오.)

inject 함수는 a, [b]를 [(a, b)]로 변환합니다. 즉, 배열의 각 값에 단일 값을 주입하여 배열의 배열을 반환합니다. a 또는 b가 이미 배열인지 여부는 중요하지 않으며 항상 2 차원 배열을 반환합니다.

inject('a', ['foo', 'bar'])
    =>  [('a', 'foo'), ('b', 'bar')]

zip 함수는 배열의 각 요소에 inject 함수를 적용합니다.

zip(['a', 'b'], ['foo', 'bar'])
    =>  [('a', 'foo'), ('a', 'bar'), ('b', 'foo'), ('b', 'bar')]

이것은 실제로 데카르트 곱을 생성하므로, zip은 약간의 잘못된 이름입니다. 연속적으로 데이터 세트의 모든 요소에이 함수를 적용하기 만하면 모든 길이의 배열에 대해 데카르트 곱을 얻을 수 있습니다.

zip(zip(['a', 'b'], ['foo', 'bar']), ['42', '76'])
    =>  [('a', 'foo', '42'), ('a', 'foo', '76'), ('a', 'bar', '42'), …]

여기에는 키가 포함되어 있지 않지만 요소가 모두 결과 집합 내에서 순서대로 있기 때문에 결과에 키를 다시 주입 할 수 있습니다.

array_combine(['key1', 'key2', 'key3'], ['a', 'foo', '42'])
    =>  [ key1 : 'a', key2 : 'foo', key3 : '42' ]

이것을 제품의 모든 요소에 적용하면 원하는 결과를 얻을 수 있습니다.

원한다면 위의 3 가지 기능을 하나의 긴 문장으로 접을 수 있습니다 (잘못된 이름도 정리할 수 있습니다).

PHP <= 5.2의 익명 함수가없는 "unrolled"버전은 다음과 같습니다.

function inject($elem, $array) {
    $elem = (array)$elem;
    foreach ($array as &$a) {
        $a = array_merge($elem, (array)$a);
    }
    return $array;
}

function zip($array1, $array2) {
    $prod = array();
    foreach ($array1 as $a) {
        $prod = array_merge($prod, inject($a, $array2));
    }
    return $prod;
}

function cartesian_product($array) {
    $keys = array_keys($array);
    $prod = array_shift($array);
    $prod = array_reduce($array, 'zip', $prod);

    foreach ($prod as &$a) {
        $a = array_combine($keys, $a);
    }
    return $prod;
}

==============================

4.재귀 적 생성기를 사용하지 않는 이유 ... 메모리 문제 : 거의 없슴 (그리고 그것은 아름답다)

재귀 적 생성기를 사용하지 않는 이유 ... 메모리 문제 : 거의 없슴 (그리고 그것은 아름답다)

function cartesian($a)
{
    if ($a)
    {
        if($u=array_pop($a))
            foreach(cartesian($a)as$p)
                foreach($u as$v)
                    yield $p+[count($p)=>$v];
    }
    else
        yield[];
}

주 : 이것은 키를 보존하지 않습니다. 그러나 그것은 시작이다.

이 작업은 수행해야합니다 (테스트하지 않음).

function acartesian($a)
{
    if ($a)
    {
        $k=end(array_keys($a));
        if($u=array_pop($a))
            foreach(acartesian($a)as$p)
                foreach($u as$v)
                    yield $p+[$k=>$v];
    }
    else
        yield[];
}

==============================

5.다른 해결책 :

다른 해결책 :

function getAllVariations($input) {
    $result = array();
    $cnt = array_product(array_map('count', $input));
    $step = 1;
    foreach ($input as $key=>$array) {
        for ($i=0; $i<$cnt; $i++) {
            foreach ($array as $value) {
                for ($k=0; $k<$step; $k++) {
                    $result[$i+$k][$key] = $value;
                }
                $i += $step;
            }
            $i--;
        }
        $step = $step * count($array);
    }
    return $result;
}

용법:

$input = array(
    'arm' => array('A', 'B', 'C'),
    'gender' => array('Female', 'Male'),
    'location' => array('Vancouver', 'Calgary'),
    'name' => array('Rio', 'Mark')
);

echo "<pre>";
var_dump(getAllVariations($input));

==============================

6.PHP 7에서 @ Serg의 대답은 다음과 같이 단축 될 수 있습니다.

PHP 7에서 @ Serg의 대답은 다음과 같이 단축 될 수 있습니다.

function cartesian(array $input)
{
    $result = [[]];
    foreach ($input as $key => $values) {
        $append = [];
        foreach ($values as $value) {
            foreach ($result as $data) {
                $append[] = $data + [$key => $value];
            }
        }
        $result = $append;
    }

    return $result;
}

==============================

7.나는 당신의 코드를 조금 빠르게 조정했다. 나의 시도는 원유 다. 나는 생각한다.

나는 당신의 코드를 조금 빠르게 조정했다. 나의 시도는 원유 다. 나는 생각한다.

$result = array();
$nm = '';
foreach ($map as $name => $a) {
    if (empty($result)) {
        $result = $a;
        $nm = $name;
        continue;
    }

    $res = array();
    foreach ($result as $r) {
        foreach ($a as $v) {
            $myr = $r;
            $myv = $v;
            if(!is_array($r)) $myr = array($nm => $r);
            if(!is_array($v)) $myv = array($name => $v);

            $res[] = array_merge($myr, $myv);
        }
    }
    $result = $res;
}
echo "<pre>";
print_r($result);

==============================

8.왜 데이터베이스를 사용하지 않습니까?

왜 데이터베이스를 사용하지 않습니까?

그것은 MySQL에서 쉽습니다 ..

table arm
   id integer primary key
   label char

table gender
   id integer primary key
   gender enum('male','female')

table location
   id integer primary key
   city varchar(255)

그런 다음 쿼리를 수행합니다.

$query = mysql_query(" 
  SELECT a.label, g.gender, l.city
  FROM arm a
  CROSS JOIN gender g
  CROSS JOIN location l
  ORDER BY a.id
") or die("Could not execute query");

while($row = mysql_fetch_array($query) )
{
   ....
}

그리고 그것을 읽으십시오 :

==============================

9.메모리 소비가 중요한 경우 또는 마지막에 모든 조합이 필요하지 않은 경우 반복자를 사용하여 한 번에 하나의 조합을 생성 할 수 있습니다. 모든 조합이 필요하면 iterator_to_array를 사용할 수 있습니다.

메모리 소비가 중요한 경우 또는 마지막에 모든 조합이 필요하지 않은 경우 반복자를 사용하여 한 번에 하나의 조합을 생성 할 수 있습니다. 모든 조합이 필요하면 iterator_to_array를 사용할 수 있습니다.

function cartezianIterator($inputArray)
{
    $maximumPosition = array_map('count', $inputArray);
    $position = array_pad([], count($inputArray), 0);

    while (false !== ($item = buildItemAtPosition($inputArray, $position))) {

        yield $item;

        $position = incrementPosition($position, $maximumPosition);
    }
}

function buildItemAtPosition($inputArray, $positions)
{
    if ($positions[0] >= count($inputArray[0])) {
        return false;
    }

    $item = [];
    foreach ($inputArray as $rowIndex => $row) {
        $position = $positions[$rowIndex];

        $item[] = $row[$position];
    }

    return $item;
}

function incrementPosition($position, $maximumPosition)
{
    $digitToIncrement = count($position) - 1;

    do {
        $position[$digitToIncrement]++;

        if ($position[$digitToIncrement] < $maximumPosition[$digitToIncrement] || 0 === $digitToIncrement) {
            //no overflow
            break;
        }

        //overflow, reset to zero and increment parent digit
        $position[$digitToIncrement] = 0;

        $digitToIncrement--;
    } while ($digitToIncrement >= 0);

    return $position;
}

그런 다음 한 번에 하나의 솔루션을 얻으려면 다음과 같이 foreach 또는 next를 사용할 수 있습니다.

$iterator = cartezianIterator($inputArray);

//of course, you need to do something with the result...
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);

몇 가지 조합 만 필요한 경우이 솔루션은 매우 빠릅니다. 또한 메모리 사용량이 매우 적습니다 (일부 정수를 저장하기 위해 평면 배열을 사용함).

참고 : 재귀 함수는 사용되지 않습니다.

==============================

10.하나의 알고리즘은 각 단계에서 현재 단계 항목으로 이전 결과를 확장하는 것입니다.

하나의 알고리즘은 각 단계에서 현재 단계 항목으로 이전 결과를 확장하는 것입니다.

function cartezian1($inputArray)
{
    $results = [];

    foreach ($inputArray as $group) {
        $results = expandItems($results, $group);
    }

    return $results;
}

function expandItems($sourceItems, $tails)
{
    $result = [];

    if (empty($sourceItems)) {
        foreach ($tails as $tail) {
            $result[] = [$tail];
        }
        return $result;
    }

    foreach ($sourceItems as $sourceItem) {
        foreach ($tails as $tail) {
            $result[] = array_merge($sourceItem, [$tail]);
        }
    }

    return $result;
}

이 솔루션은 메모리를 사용하여 모든 조합을 저장 한 다음 한 번에 모두 반환합니다. 따라서 속도는 빠르지 만 많은 메모리가 필요합니다. 또한 재귀 함수는 사용되지 않습니다.

from https://stackoverflow.com/questions/6311779/finding-cartesian-product-with-php-associative-arrays by cc-by-sa and MIT license

'PHP' 카테고리의 다른 글

내 문자열의 특정 부분을 대체하는 방법? (0)	2018.09.08
치명적 오류 : 비 객체의 fetch_assoc () 멤버 함수 호출 (0)	2018.09.08
PHP로 날짜별로 파일 정렬 (0)	2018.09.08
PHP에서 배열의 중복 값을 제거하는 방법 (0)	2018.09.08
PHP에서 빈 값으로부터 기본 객체를 생성 하시겠습니까? (0)	2018.09.08

복붙노트

PHP associative arrays를 이용한 데카르트 제품 찾기

PHP associative arrays를 이용한 데카르트 제품 찾기

해결법

1.여기에 내가 부끄러워하지 않을 해결책이 있습니다.

2.다음은 @ Jon의 직교 함수 최적화 된 버전입니다.

3.여기에 내가 생각해 낼 수있는 것이있다.

4.재귀 적 생성기를 사용하지 않는 이유 ... 메모리 문제 : 거의 없슴 (그리고 그것은 아름답다)

5.다른 해결책 :

6.PHP 7에서 @ Serg의 대답은 다음과 같이 단축 될 수 있습니다.

7.나는 당신의 코드를 조금 빠르게 조정했다. 나의 시도는 원유 다. 나는 생각한다.

8.왜 데이터베이스를 사용하지 않습니까?

9.메모리 소비가 중요한 경우 또는 마지막에 모든 조합이 필요하지 않은 경우 반복자를 사용하여 한 번에 하나의 조합을 생성 할 수 있습니다. 모든 조합이 필요하면 iterator_to_array를 사용할 수 있습니다.

10.하나의 알고리즘은 각 단계에서 현재 단계 항목으로 이전 결과를 확장하는 것입니다.

'PHP' 카테고리의 다른 글

티스토리툴바