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
    Commented 8 окт. 2012 в 1:57
0

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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