دنباله های متوالی جایگشت، کسی هست؟ (PWC 294)

Summarize this content to 400 words in Persian Lang
چالش 294 راه حل در پرل توسط ماتیاس موث

اینها راه حل های چالش 294 تسک 1 و 2 من در پرل هستندبرای چالش هفتگی – پرل و راکو.

خلاصه

وظیفه 1: دنباله های متوالی

O(n)O(n) O(n)

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

وظیفه 2: جایگشت بعدیکار “محلی” برای برگرداندن اعداد برای بدست آوردن جایگشت بعدی، بدون نیاز به ایجاد همه جایگشت ها ابتدا.

کد:کد منبع کامل هر دو کار، از جمله تست های بیشتر را در Github پیدا کنید.

وظیفه 1: دنباله متوالی

به شما یک آرایه مرتب نشده از اعداد صحیح، @ints داده می شود.یک اسکریپت بنویسید تا طول طولانی ترین دنباله عناصر متوالی را برگرداند. اگر هیچ کدام پیدا نشد -1 را برگردانید. الگوریتم باید در زمان O(n) اجرا شود.

مثال 1ورودی: @ints = (10، 4، 20، 1، 3، 2)خروجی: 4طولانی ترین دنباله متوالی (1، 2، 3، 4).طول دنباله 4 است.

مثال 2ورودی: @ints = (0، 6، 1، 8، 5، 2، 4، 3، 0، 7)خروجی: 9

مثال 3ورودی: @ints = (10، 30، 20)خروجی: -1

اوه بزرگ آه.

O(n)O(n) O(n)

!

این محدودیت به این معنی است که ساده ترین راه حل، مرتب کردن آرایه و سپس قدم زدن در میان اعداد مرتب شده است نه مجاز است. به این دلیل است sort دارای یک

O(nورود به سیستم⁡n)O(n \log{} n) O(nاینجاgn)

پیچیدگی زمانی

پس چه ما هستند مجاز به انجام برای

O(n)O(n) O(n)

راه رفتن از طریق آرایه است. تا زمانی که از حلقه دیگری در یک حلقه استفاده نکنیم، حتی می توانیم چندین بار در آرایه قدم بزنیم. این فقط به این معنی است که زمان اجرا صرف شده برای هر عدد کمی بیشتر است، اما هنوز هم مقیاس می شود به صورت خطی با افزایش

nn n

. در واقع

O(2n)O(2n) O(2n)

همان است که

O(n)O(n)O(n)

.

در واقع من انجام دهید دو بار از طریق داده ها قدم بزنید! استفاده می کنم uniq در داده های ورودی، به عنوان اولین پاس (مثال 2 شامل a 0 دو بار!). من این کار را انجام می دهم تا مطمئن شوم که ورودی های دوتایی در تشخیص توالی ها اختلال ایجاد نمی کنند.

بیایید یک «سکانس متوالی» را به اختصار «رگه» بنامیم.ما باید در هنگام مواجهه با اعداد، یک به یک “رگه ها” را ایجاد کنیم.ساختار داده ای که من برای نمایش یک رگه استفاده می کنم یک هش ساده است:

$streak = { FROM => $a, TO => $b };

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

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

برای دانستن اینکه آیا آن رگه های همسایه از قبل وجود دارند یا خیر، من یک هش جستجو نگه می دارم، %streaks. برای هر رگه ای که ایجاد می کنم، یک ارجاع به ساختار داده رگه را در آن هش جستجو قرار می دهم، یکی با شماره شروع آن به عنوان کلید، و دیگری با شماره پایان آن. بنابراین، برای دسترسی به رگه های همسایه چپ و راست برای هر عدد جدید $n، فقط باید بررسی کنم $streaks{ $n – 1 } و $streaks{ $n + 1 }.. و هنگامی که آن ها را داشته باشم، «سایر انتهای» آنها را می دانم: شماره شروع رگه سمت چپ، و شماره پایان رگه راست. سپس می توانم یک رگه جدید ایجاد کنم که همه آنها را پوشش دهد، رگه سمت چپ، شماره جدید و رگه سمت راست (اگر وجود داشته باشد، یعنی).

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

برای برگرداندن طول طولانی‌ترین رگه در پایان، بررسی می‌کنم که آیا نوار جدید طولانی‌تر از آنچه قبلاً داریم است یا خیر، و بر این اساس به‌روزرسانی می‌کنم.

من نظرات را در داخل کد گذاشته ام تا دنبال کردن آن راحت تر باشد:

use v5.36;
use List::Util qw( uniq );

sub consecutive_sequence_using_hash( @ints ) {
my $max_streak_length = -1;
my %streaks;
for my $n ( uniq @ints ) {
# Create a new streak from this number,
# possibly merged with any existing adjacent streaks
# to the left or to the right.
my ( $left, $right ) =
( $streaks{ $n – 1 }, $streaks{ $n + 1 } );
my ( $from, $to ) = (
$left ? $left->{FROM} : $n,
$right ? $right->{TO} : $n,
);
my $streak = { FROM => $from, TO => $to };

# Update the lookup entries:
# Remove any entries that are *inside* the merged streak,
# and add or update entries at the streak borders.
delete $streaks{ $left->{TO} }
if $left;
delete $streaks{ $right->{FROM} }
if $right;
$streaks{$from} = $streaks{$to} = $streak;

# Update the maximum length if this is a streak
# (not just a single number) and it’s longer than what we have.
$max_streak_length = $to – $from + 1
if $to > $from && $to – $from + 1 > $max_streak_length;
}
return $max_streak_length;
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

بدون حلقه در داخل!به نظر من این کار درستی است

O(n)O(n) O(n)

راه حل

وظیفه 2: جایگشت بعدی

آرایه ای از اعداد صحیح به شما داده می شود، @ints.یک اسکریپت بنویسید تا جایگشت بعدی آرایه داده شده را پیدا کنید.جایگشت بعدی آرایه ای از اعداد صحیح، جایگشت بعدی از نظر واژگانی بزرگتر عدد صحیح آن است.

مثال 1ورودی: @ints = (1، 2، 3)خروجی: (1، 3، 2)جایگشت های (1، 2، 3) که از نظر لغوی مرتب شده اند:(1، 2، 3)(1، 3، 2)(2، 1، 3)(2، 3، 1)(3، 1، 2)(3، 2، 1)

مثال 2ورودی: @ints = (2، 1، 3)خروجی: (2، 3، 1)

مثال 3ورودی: @ints = (3، 1، 2)خروجی: (3، 2، 1)

یک راه حل ساده اما محاسباتی فشرده ایجاد خواهد بود همه جایگشت اعداد درگیر، سپس آنها را مرتب کنید (“از نظر لغوی”)، سپس ورودی را پیدا کنید که با جایگشت داده شده مطابقت دارد، و سپس ورودی بعدی را برگردانید.در واقع من این رویکرد را زیاد دوست ندارم، زیرا در تجربه من، هر چیزی که با جایگشت یا ترکیب ربط داشته باشد، تمایل زیادی به استفاده از زمان زیاد، یا حافظه زیاد، یا هر دو، بسیار سریع دارد.

بیایید راه حلی پیدا کنیم که “محلی” کار کند!

برای تغییر جایگشت موجود به جایگشت بالاتر بعدی، باید عددی را با کمترین اهمیت قابل افزایش پیدا کنیم.این بدان معناست که ما از انتهای سمت راست شروع می کنیم (کمترین مقدار) و اولین عددی را پیدا می کنیم که از همسایه سمت راستش کمتر است. همه اعداد سمت راست آن مرتب شده اند، در ابتدا بالاترین، بنابراین نمی توان آنها را “افزایش” کرد.

اگر ما نکرد هر عددی را پیدا کنید که از همسایه سمت راستش کمتر باشد؟در آن صورت، همه اعداد مرتب شده اند، ابتدا بالاترین. این باید آخرین جایگشت ممکن باشد. به این معنی که جایگشت بعدی از ابتدای چرخه همه جایگشت ها دوباره شروع می شود.در جایگشت اول، ابتدا اعداد کمترین مرتبه می شوند. برای رسیدن به آنجا، فقط می توانیم معکوس بالاترین دنباله جایگشت اعداد، و ما می توانیم آن را به عنوان نتیجه برگردانیم.

اگر اینطور نیست، و عددی را پیدا کرده‌ایم که می‌تواند «افزایش» شود، باید عدد بالاتر بعدی را پیدا کنیم تا این عدد را جایگزین کنیم.ما فقط در قسمت سمت راست جایگشت نگاه می کنیم، زیرا استفاده از هر عددی از سمت چپ، ترتیب را بیش از آنچه می خواهیم تغییر می دهد.ما به دنبال کمترین عدد ممکن هستیم که هنوز از تعداد ما بیشتر باشد.

هنگامی که شماره جایگزین را پیدا کردیم، دو عدد را با هم عوض می کنیم.سپس تعداد خود را با مقدار بالاتر احتمالی بعدی همه جایگشت های قسمت سمت راست “افزایش” داده ایم. در عین حال، شماره جایگزینی را به عدد کمتر ممکن بعدی کاهش داده ایم. بنابراین ترتیب قسمت سمت راست همچنان «بالاترین به پایین‌ترین» است. از آنجایی که به جایگشت «اول» قسمت سمت راست نیاز داریم، می‌توانیم آن را معکوس کنیم.

همین! ما کمترین افزایش ممکن را پیدا کرده ایم.

باز هم برای دنبال کردن راحت تر نظرات را در کد گذاشته ام.

use v5.36;

sub next_permutation( @ints ) {
return @ints
if @ints <= 1;

# Starting from the end, find the first number
# that is lower than the one following it.
my $index = $#ints;
while( $index > 0 && $ints[ –$index ] gt $ints[ $index + 1 ] ) {
# Everything is in the loop condition.
}

# No lower number found?
# Then we are at the end of the permutations.
return reverse @ints
if $index == 0;

my $value = $ints[$index];

# Find the next highest value within the right part,
# for using it to replace the current value.
# (Remember that maybe not all values in the right part are higher!)
# It has to be higher than the one to substitute, but the
# lowest possible one.
my ( $index_2, $replacement ) = ( $index + 1, $ints[ $index + 1 ] );
for ( $index_2 + 1 .. $#ints ) {
( $index_2, $replacement ) = ( $_, $ints[$_] )
if $value lt $ints[$_] lt $replacement;
}

# Swap the two numbers.
@ints[ $index, $index_2 ] = @ints[ $index_2, $index ];

# We know that the right side is sorted, highest first.
# to have it sorted lowest first, we just need to reverse it.
@ints[ $index + 1 .. $#ints ] =
reverse @ints[ $index + 1 .. $#ints ];

return @ints;
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اگر این را چندین بار متوالی اجرا کنیم، یک “توالی متوالی جایگشت” دریافت خواهیم کرد.چه خوب برای عنوان این وبلاگ، ترکیب این دو کار!

از شما برای چالش متشکرم!

کد منبع کامل هر دو کار، از جمله تست‌ها را در Github پیدا کنید.

    $streak = { FROM => $a, TO => $b };

use v5.36;
use List::Util qw( uniq );

sub consecutive_sequence_using_hash( @ints ) {
    my $max_streak_length = -1;
    my %streaks;
    for my $n ( uniq @ints ) {
        # Create a new streak from this number,
        # possibly merged with any existing adjacent streaks
        # to the left or to the right.
        my ( $left, $right ) =
            ( $streaks{ $n - 1 }, $streaks{ $n + 1 } );
        my ( $from, $to ) = (
            $left ? $left->{FROM} : $n,
            $right ? $right->{TO} : $n,
        );
        my $streak = { FROM => $from, TO => $to };

        # Update the lookup entries:
        # Remove any entries that are *inside* the merged streak,
        # and add or update entries at the streak borders.
        delete $streaks{ $left->{TO} }
            if $left;
        delete $streaks{ $right->{FROM} }
            if $right;
        $streaks{$from} = $streaks{$to} = $streak;

        # Update the maximum length if this is a streak
        # (not just a single number) and it's longer than what we have.
        $max_streak_length = $to - $from + 1
            if $to > $from && $to - $from + 1 > $max_streak_length;
    }
    return $max_streak_length;
}

use v5.36;

sub next_permutation( @ints ) {
    return @ints
        if @ints <= 1;

    # Starting from the end, find the first number
    # that is lower than the one following it.
    my $index = $#ints;
    while( $index > 0 && $ints[ --$index ] gt $ints[ $index + 1 ] ) {
        # Everything is in the loop condition.
    }

    # No lower number found?
    # Then we are at the end of the permutations.
    return reverse @ints
        if $index == 0;

    my $value = $ints[$index];

    # Find the next highest value within the right part,
    # for using it to replace the current value.
    # (Remember that maybe not all values in the right part are higher!)
    # It has to be higher than the one to substitute, but the
    # lowest possible one.
    my ( $index_2, $replacement ) = ( $index + 1, $ints[ $index + 1 ] );
    for ( $index_2 + 1 .. $#ints ) {
        ( $index_2, $replacement ) = ( $_, $ints[$_] )
            if $value lt $ints[$_] lt $replacement;
    }

    # Swap the two numbers.
    @ints[ $index, $index_2 ] = @ints[ $index_2, $index ];

    # We know that the right side is sorted, highest first.
    # to have it sorted lowest first, we just need to reverse it.
    @ints[ $index + 1 .. $#ints ] =
        reverse @ints[ $index + 1 .. $#ints ];

    return @ints;
}