بدست آوردن زیر مجموعه های یک مجموعه در php

۵ سال پیش(به روز شده در ۴ سال پیش) پی اچ پی(PHP)(توابع) ۰

تابع ()subsets زیر مجموعه های یک مجموعه را بر می گرداند. روش کار الگوریتم بسیار ساده است. ابتدا با توجه به آرایه ورودی تعداد اعضای آرایه را بدست می آوریم و سپس 2 را بتوان آن عدد می رسانیم. در واقع یک مجموعه n عضوی دارای 2n عضو است. به هر حال ، با استفاده از شمارش دودویی شروع به بدست آوردن زیر مجموعه ها می کنیم. یعنی از 1 تا 1-2n بصورت دودویی شمارش می کنیم(توجه: تهی نیز یک زیر مجموعه بحساب می آید).

1, 2, 3, 4, ...

00001, 00010, 00011, 00100, ...

حال تعداد ارقام دودویی را بر اساس تعداد اعضای آرایه قرار می دهیم. آرایه ما بشکل زیر است(در پی اچ پی شمارش از صفر شروع می شود):

0 1 2
A B C

آرایه ما 3 عضوی است یعنی 8 زیر مجموعه دارد و لذا با در نظر گرفتن تعداد 3 رقمی کد باینری مان ، شمارش را از 1 تا خود 7 شروع می کنیم و به ازای هر 1 ، مقدار موجود در آرایه با توجه شماره خانه فراخوانی می کنیم. بهتر است مثال را ببینید(مجموعه تهی را نیز فراموش نکنید!):

1 2 3 4 5 6 7
001 010 011 100 101 110 111
C B BC A AC AB ABC
function subsets( $items ) {
    $result = array() ;
    $num = count( $items ) ;
    $members = pow( 2, $num ) ;
    for ( $i = 0; $i < $members; $i++ ) {
        $b = sprintf( "%0" . $num . "b", $i ) ;
        $tmp = array() ;
        for ( $j = 0; $j < $num; $j++ ) {
            if ( $b[$j] == '1' ) {
                $tmp[] = $items[$j] ;
            }
        }
        if ( $tmp ) {
            sort( $tmp ) ;
            $result[] = $tmp ;
        }
    }
    return $result ;
}
 
$items = array('A', 'B', 'C' ) ;
print_r( subsets( $items ) ) ;

/*Out
Array
(
    [0] => Array
        (
            [0] => C
        )

    [1] => Array
        (
            [0] => B
        )

    [2] => Array
        (
            [0] => B
            [1] => C
        )

    [3] => Array
        (
            [0] => A
        )

    [4] => Array
        (
            [0] => A
            [1] => C
        )

    [5] => Array
        (
            [0] => A
            [1] => B
        )

    [6] => Array
        (
            [0] => A
            [1] => B
            [2] => C
        )

)
*/

 

صفحات پیشنهادی

مرتب سازی آرایه های چند بعدی با استفاده از اندیس خاص (sort array)...

تابع زیر آرایه مورد نظر را با توجه به اندیس ورودی مرتب سازی می کند. ورودی اول مربوط به آرایه , ورودی دوم مربوط به اندیس ای است که باید بر اساس آن مرتب سازی صورت گیرد و بخش سوم صعودی یا نزولی بودن ترتی...

ترجمه اعداد به رشته کوتاه...

گاهی لازم است عددهای بزرگ را خلاصه و یا به اصطلاح ترجمه کرد. ما به عمد تمام جزییات را به دلیل حق انحصار برنامه نویس درج کرده ایم (به مثال آخر نوشته دقت شود). توجه شود که هر چه مقدار متغیر index$ بیشتر...

تبدیل فوت به کیلومتر در php...

تابع تبدیل واحد فوت به کیلومتر در زبان php......

تابع subwords - نمایش بخشی از کلمه های یک رشته...

در php تابعی بعنوان substr برای نمایش یک رشته وجود دارد. اینبار تابعی را معرفی می کنیم که بخشی از کلمات یک رشته را با توجه به تعداد مشخص شده ورودی بر می گرداند. مزیت این تابع این است که از رشته های یو...

نظر

نظری ثبت نشده است.
captcha image reload