بدست آوردن زیر مجموعه های یک مجموعه در 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
        )

)
*/

 

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

تابع utf8SubString , گرفتن بخشی از رشته با یونیکد UTF8...

تابع معمولی substr در php برای رشته های یونیکدی جواب نمی دهد. در واقع در رشته های یونیکد دار هر حرف از ترکیب سه یا چهار حرف اسکی که کد اسکی آنها بیشتر از 127 است تشکیل شده است. لذا نیاز است تا برای ای...

مرتب سازی آرایه های چند متغیری و چند بعدی در php...

تابع زیر مرتب سازی یک آرایه با چندین مقدار برای هر ایندکس و آرایه چند بعدی را با اعمال محدودیت انجام میدهد. میتوانید با اندکی تغییر آنرا پیشرفته تر کنید!......

تابع تبدیل حجم فایل به بایت با توجه به فرمت آن...

با استفاده از تابع زیر می توانید حجم فایل سایز ورودی که می تواند به همراه فرمت باشد را به بایت بدست آورید. بعنوان مثال شما می توانید حداکثر حجم فایل برای آپلود که در php.ini تنظیم شده است را به بایت ب...

گرفتن جملات یک رشته...

این تابع جملات رشته ورودی را بر می گرداند. آرگومان str$ رشته ورودی و char$ مربوط به جدا کننده کلمات در رشته می باشد که به طور پیش فرض تهی است. function parser($str, $char = ' ') { $str = trim($str...

نظر

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