Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > PHP: Общие вопросы > Помогите написать алгоритм

Автор: Scorpion75 25.9.2009, 22:40

Всем привет.
Есть например строка:

12-1-13-132-2-3-3-2-12-13-2-3-3-1-2

Мне надо ее разложить на строки, в которых только одиночные значения

Т.е. строку 1-1-1-1-1-1-1-1-1-1-1-1-1-1-12 разложим на 2 строки

1-1-1-1-1-1-1-1-1-1-1-1-1-1-1
1-1-1-1-1-1-1-1-1-1-1-1-1-1-2

Кол-во таких одиночных строк определяется по формуле 2^n*3^m, где n, m-количество элементов с 2мя и 3мя значениями соответственно

Сам пока реализовал, тупо перебирая через вложенные циклы

Код

$ishod=explode ("-", $stroka);
    $size_kupon=sizeof ($ishod);

    for ($i=0; $i<$size_kupon; $i++) {
        $size_ishod [$i]=strlen ($ishod[$i]);
    }

    for ($z0=0; $z0<$size_ishod [0]; $z0++) {
        $ish[0] = substr($ishod[0], $z0, 1);
        for ($z1=0; $z1<$size_ishod [1]; $z1++) {
            $ish[1] = substr($ishod[1], $z1, 1);
            for ($z2=0; $z2<$size_ishod [2]; $z2++) {
                $ish[2] = substr($ishod[2], $z2, 1);
                for ($z3=0; $z3<$size_ishod [3]; $z3++) {
                    $ish[3] = substr($ishod[3], $z3, 1);
                    for ($z4=0; $z4<$size_ishod [4]; $z4++) {
                        $ish[4] = substr($ishod[4], $z4, 1);
                        for ($z5=0; $z5<$size_ishod [5]; $z5++) {
                            $ish[5] = substr($ishod[5], $z5, 1);
                            for ($z6=0; $z6<$size_ishod [6]; $z6++) {
                                $ish[6] = substr($ishod[6], $z6, 1);
                                for ($z7=0; $z7<$size_ishod [7]; $z7++) {
                                    $ish[7] = substr($ishod[7], $z7, 1);
                                    for ($z8=0; $z8<$size_ishod [8]; $z8++) {
                                        $ish[8] = substr($ishod[8], $z8, 1);
                                        for ($z9=0; $z9<$size_ishod [9]; $z9++) {
                                            $ish[9] = substr($ishod[9], $z9, 1);
                                            for ($z10=0; $z10<$size_ishod [10]; $z10++) {
                                                $ish[10] = substr($ishod[10], $z10, 1);
                                                for ($z11=0; $z11<$size_ishod [11]; $z11++) {
                                                    $ish[11] = substr($ishod[11], $z11, 1);
                                                    for ($z12=0; $z12<$size_ishod [12]; $z12++) {
                                                        $ish[12] = substr($ishod[12], $z12, 1);
                                                        for ($z13=0; $z13<$size_ishod [13]; $z13++) {
                                                            $ish[13] = substr($ishod[13], $z13, 1);
                                                            for ($z14=0; $z14<$size_ishod [14]; $z14++) {
                                                                $ish[14] = substr($ishod[14], $z14, 1);

                                                                                                                    
                                                                $new_stroka="";
                                                                for ($i=0; $i<15; $i++) {
                                                                    $new_stroka.=$ish[$i];
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Но при большом количестве строк получаются жуткие тормоза

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

Автор: nerezus 25.9.2009, 23:24

Я не понял, что ты хочешь, но вот по ссылке тебе ОБЯЗАТЕЛЬНО надо читать.

http://ru.wikipedia.org/wiki/Рекурсия

Автор: Simpliest 26.9.2009, 00:06

Цитата(Scorpion75 @ 25.9.2009, 22:40

)

Т.е. строку 1-1-1-1-1-1-1-1-1-1-1-1-1-1-12 разложим на 2 строки

1-1-1-1-1-1-1-1-1-1-1-1-1-1-1
1-1-1-1-1-1-1-1-1-1-1-1-1-1-2

Логики не понял

как мы получили эти две строки? smile

Автор: NightmareZ 26.9.2009, 00:46

Цитата(Scorpion75 @ 25.9.2009, 22:40

)

Может у кого-нить есть идея получше, как это можно организовать?

Каюсь, на похапэ писал очень давно и тупо не помню нужных мне функций, а гуглить неохото. Ибо.
Потому привожу код на C#.

Код


using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string baseString = Console.ReadLine();
            var arr = baseString.Split('-');
            var counter = new int[arr.Length];
            counter[counter.Length - 1] = -1;

            while (true)
            {
                counter[counter.Length - 1]++;

                for (int i = counter.Length - 1; i > 0; i--)
                {
                    if (counter[i] >= arr[i].Length)
                    {
                        counter[i] = 0;
                        counter[i - 1]++;
                    }
                }

                if (counter[0] >= arr[0].Length)
                    break;

                for (int i = 0; i < arr.Length; i++)
                {
                    Console.Write(arr[i][counter[i]]);
                    if (i != arr.Length - 1)
                        Console.Write("-");
                }
                Console.WriteLine();
            }

            Console.ReadKey();
        }
    }
}

Например, твоя строка 12-1-13-132-2-3-3-2-12-13-2-3-3-1-2 раскладывается в:

Код


1-1-1-1-2-3-3-2-1-1-2-3-3-1-2
1-1-1-1-2-3-3-2-1-3-2-3-3-1-2
1-1-1-1-2-3-3-2-2-1-2-3-3-1-2
1-1-1-1-2-3-3-2-2-3-2-3-3-1-2
1-1-1-3-2-3-3-2-1-1-2-3-3-1-2
1-1-1-3-2-3-3-2-1-3-2-3-3-1-2
1-1-1-3-2-3-3-2-2-1-2-3-3-1-2
1-1-1-3-2-3-3-2-2-3-2-3-3-1-2
1-1-1-2-2-3-3-2-1-1-2-3-3-1-2
1-1-1-2-2-3-3-2-1-3-2-3-3-1-2
1-1-1-2-2-3-3-2-2-1-2-3-3-1-2
1-1-1-2-2-3-3-2-2-3-2-3-3-1-2
1-1-3-1-2-3-3-2-1-1-2-3-3-1-2
1-1-3-1-2-3-3-2-1-3-2-3-3-1-2
1-1-3-1-2-3-3-2-2-1-2-3-3-1-2
1-1-3-1-2-3-3-2-2-3-2-3-3-1-2
1-1-3-3-2-3-3-2-1-1-2-3-3-1-2
1-1-3-3-2-3-3-2-1-3-2-3-3-1-2
1-1-3-3-2-3-3-2-2-1-2-3-3-1-2
1-1-3-3-2-3-3-2-2-3-2-3-3-1-2
1-1-3-2-2-3-3-2-1-1-2-3-3-1-2
1-1-3-2-2-3-3-2-1-3-2-3-3-1-2
1-1-3-2-2-3-3-2-2-1-2-3-3-1-2
1-1-3-2-2-3-3-2-2-3-2-3-3-1-2
2-1-1-1-2-3-3-2-1-1-2-3-3-1-2
2-1-1-1-2-3-3-2-1-3-2-3-3-1-2
2-1-1-1-2-3-3-2-2-1-2-3-3-1-2
2-1-1-1-2-3-3-2-2-3-2-3-3-1-2
2-1-1-3-2-3-3-2-1-1-2-3-3-1-2
2-1-1-3-2-3-3-2-1-3-2-3-3-1-2
2-1-1-3-2-3-3-2-2-1-2-3-3-1-2
2-1-1-3-2-3-3-2-2-3-2-3-3-1-2
2-1-1-2-2-3-3-2-1-1-2-3-3-1-2
2-1-1-2-2-3-3-2-1-3-2-3-3-1-2
2-1-1-2-2-3-3-2-2-1-2-3-3-1-2
2-1-1-2-2-3-3-2-2-3-2-3-3-1-2
2-1-3-1-2-3-3-2-1-1-2-3-3-1-2
2-1-3-1-2-3-3-2-1-3-2-3-3-1-2
2-1-3-1-2-3-3-2-2-1-2-3-3-1-2
2-1-3-1-2-3-3-2-2-3-2-3-3-1-2
2-1-3-3-2-3-3-2-1-1-2-3-3-1-2
2-1-3-3-2-3-3-2-1-3-2-3-3-1-2
2-1-3-3-2-3-3-2-2-1-2-3-3-1-2
2-1-3-3-2-3-3-2-2-3-2-3-3-1-2
2-1-3-2-2-3-3-2-1-1-2-3-3-1-2
2-1-3-2-2-3-3-2-1-3-2-3-3-1-2
2-1-3-2-2-3-3-2-2-1-2-3-3-1-2
2-1-3-2-2-3-3-2-2-3-2-3-3-1-2

З.Ы. Спасибо за интересую задачу.

Автор: youri 26.9.2009, 02:01

Код


<?php

$s = '12-1-13-132-2-3-3-2-12-13-2-3-3-1-2';
$els = explode( '-', $s );
var_dump( scan( $els ) );

function scan( $a ) {

    $cur = array_shift( $a );
    $cur = str_split( $cur );
    if (! $a)
        return $cur;
    $other = scan( $a );
    $r = array();
    for( $i=0; $i<count($cur); $i++ )
        for( $j=0; $j<count($other); $j++ )
           $r[] = $cur[ $i ].'-'.$other[ $j ];
    return $r;
}

Автор: Scorpion75 27.9.2009, 21:06

Цитата(nerezus)

Я не понял, что ты хочешь, но вот по ссылке тебе ОБЯЗАТЕЛЬНО надо читать.

http://ru.wikipedia.org/wiki/Рекурсия

Спасибо за ссылку, обязательно постараюсь в этом разобраться

Добавлено @ 21:20

Цитата(Simpliest @ 26.9.2009, 00:06)

Цитата(Scorpion75 @ 25.9.2009, 22:40

)

Т.е. строку 1-1-1-1-1-1-1-1-1-1-1-1-1-1-12 разложим на 2 строки

1-1-1-1-1-1-1-1-1-1-1-1-1-1-1
1-1-1-1-1-1-1-1-1-1-1-1-1-1-2

Логики не понял

как мы получили эти две строки? smile

Смысл в том, что надо получить строки с одиночными значениями

Пример:
есть строка 1-2-34
ее можно разложить на 2 строки
1-2-3
1-2-4, т.е. последнее значение исходной строки, состоящее из 2х цифр раскладывается на одиночные

Как я писал, все раскладывается по формуле 2^n*3^m, где n, m-количество элементов с 2мя и 3мя значениями соответственно

В исходной строке n=1 (элемент 34 состоит из 2х цифр), m=0 (элементов из 3х цифр нет), значит 2^1=2 и получаем 2 строки

У меня строки из 15 элементов, каждый элемент может состоять из 3х значений , выходит более 14 000 000 комбинаций, вот и нужен оптимальный алгоритм раскладывания

Автор: Scorpion75 27.9.2009, 21:29

Цитата(youri @ 26.9.2009, 02:01)

Код


<?php

$s = '12-1-13-132-2-3-3-2-12-13-2-3-3-1-2';
$els = explode( '-', $s );
var_dump( scan( $els ) );

function scan( $a ) {

    $cur = array_shift( $a );
    $cur = str_split( $cur );
    if (! $a)
        return $cur;
    $other = scan( $a );
    $r = array();
    for( $i=0; $i<count($cur); $i++ )
        for( $j=0; $j<count($other); $j++ )
           $r[] = $cur[ $i ].'-'.$other[ $j ];
    return $r;
}

По этому коду выдается ошибка
Fatal error: Call to undefined function: str_split() in z:\home\test1.ru\www\qqq.php on line 8
Вызов неопределенной функции, насколько я правильно понимаю

У меня версия рнр 4

Выложил на хостинг, тоже самое, там рнр 4.4.9
В чем может быть проблема? Работает только в рнр 5?

Автор: Scorpion75 27.9.2009, 22:14

Вместо

Код


$cur = str_split( $cur );

Использовал

Код


$cur = preg_split('//', $cur, -1, PREG_SPLIT_NO_EMPTY);

Вроде получилось.
Спасибо за помощь

З.Ы. если будут еще варианты, то пишите