1

Здравствуйте! Столкнулся с такой вот проблемкой. Мне необходимо динамически создавать ассоциативный массив получая от пользователя 1 параметр, число, а точнее количество классов устройства.Например пользователь вводит число 3, т.е. 3 класса устройства. Каждый класс может быть реализован на процессоре или на микросхеме, т.е. значение класса n может быть 1 или 0. Мне нужно получать массив содержащий все возможные комбинации чисел 1 и 0 "длинной" n. Я получаю на входе число n, затем получаю общее число возможных комбинаций, 2 в степени n . Запускаю цикл, в котором генерирую элемент i-ой строки массива (массив 2-х мерный должен быть)

$arr[$i]["Class".$j.""] = rand(0,1);

переменная $j в моём случае принимает значения от 1 до n включительно. Т.е. нор класса в i-q строке. Параллельно с этим я записываю строковую переменную "Ключ".

$key .= $arr[$i]["Class".$j.""];

Она потребуется для сравнения с уже существующей записью в массиве. Т.е. к примеру у меня получилась такая комбинация классов {1;0;1} при этом ключ будет равен string(3)"101", его я и буду в цикле проверять с другими ключами массива и в случае НЕ совпадения, записывать "симплекс" в массив. Логика вначале мне показалась правильной, но затем я засомневался. Потому как как-то не правильно вначале я записываю классы, собираю ключ, сравниваю ключ, не совпал - записываю, совпал - удаляю классы котороые записал перед сравнением. Может у кого-то есть идея реализации такого алгоритма?

На вход число n (количество классов), на выходе вот такая матрица:

class1|class2|class3|classn|Key|
|1|0|1|..|n|101|
------------
|1|0|0|..|n|100|  
------------
|0|0|0|..|n|000|
------------
|0|1|0|..|n|010|

.... и т.д.

при этом строки или ключи (т.к. ключи это "псевдоним" строки) - уникальные. Заранее спасибо!

3 ответа 3

4

Похоже, нужна ф-я, которая возвращает массив со всеми комбинациями единиц и нулей длиной N. Т.е. все возможные числа в двоичной записи длиной N бит.

Для N<32 ( <64 для 64-битных систем) можно так «перебрать» все варианты:

function allCombs( $n){
    if( $n > PHP_INT_SIZE * 8) {
        echo '$n слишком длинна для этого компа';
        return;
    }
    $result = array();
    $max = 1 << $n; // максимум: $n единиц
    $format = '%0' .$n. 'b';    
    for( $i=0; $i < $max; $i++){
        $bin = sprintf( $format, $i); // строка из 0 и 1 длиной N
        $set = str_split( $bin); // массив из 1 и 0 
        array_push( $set, $bin); // +последний элемент строка-ключ
        array_push( $result, $set);
    }
    return $result;
}

Вывод для N=3:

0, 0, 0, 000
0, 0, 1, 001
0, 1, 0, 010
0, 1, 1, 011
1, 0, 0, 100
1, 0, 1, 101
1, 1, 0, 110
1, 1, 1, 111
1

На сколько я понял, это задача нахождения всех подмножеств заданного исходного множества. Просто исходное множество задается путем установления длинны.

Например, пользователь вводит число 3, это значит что исходное множество {1,2,3}. Если число 5, то {1,2,3,4,5}.

Например, для множества {1,2,3} подмножествами будут {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

Данная задача решается через двоичную систему. В двоичной системе создается число, которое представляет из себя что-то типа маски вхождения элементов, например первое такое число [001]. Тогда согласно этой маске в подмножества будет выведено {3}. Далее к маске прибавляется 'единица' и повторяется вывод по ней: [010] = {2}. В итоге получает так:

{1,2,3} * [001] = {3}
{1,2,3} * [010] = {2}
{1,2,3} * [011] = {2,3}
{1,2,3} * [100] = {1}
{1,2,3} * [101] = {1,3}
{1,2,3} * [110] = {1,2}
{1,2,3} * [111] = {1,2,3}

Каким образом это должно быть реализовано на Вашем языке программирования, я думаю, что Вы сами придумаете.

1
  • ТС интересует строка постоянной длины, из всех возможных сочетаний 1 и 0, вроде бы. Всё просто, не стоит отвлекаться на более сложные подмножества вариативной длины )
    – Sergiks
    8 окт 2012 в 1:57
0

Если я правильно вас понял, то использование rand в вашем случае абсолютно неверно, теоретически вы можете никогда не выйти из цикла.

Погуглите Комбинаторика

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.