STL istifadə edərək verilmiş bir simlin perermutasiyaları

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma ByteDance eBay Facebook google microsoft Kahin
Permutasiya STL SimBaxılıb 244

Problem bəyanat

"STL istifadə edərək verilən bir simlin perermutasiyası" problemində, a sim "S". STL funksiyalarından istifadə edərək giriş sətrinin bütün permutasiyalarını çap edin.

Giriş Formatı

"S" simli olan ilk və yalnız bir sətir.

Çıxış formatı

Verilən sətrin bütün permutasiyasını hər sətirdə yalnız bir simli olduğu yerdə çap edin.

Məhdudiyyətlər

  •  1 <= | s | <= 10
  • s [i] kiçik İngilis əlifbası olmalıdır

misal

ABC
ABC
ACB
BCA
BAC
CAB
CBA

Explanation: Burada ümumi 3 * 2 * 1 permütasiya var. Əməliyyatlar etdikdən sonra cavab olaraq ABC, ACB, BCA, BAC, CAB, CBA əldə edirik.

Pin

STL istifadə edərək verilmiş bir simli perermutasiya alqoritmi

Permutasiya ayrıca "tənzimləmə nömrəsi" və ya "sifariş" adlanır, S sıralanmış siyahının elementlərinin S-nin özü ilə təkbətək bir yazışmaya çevrilməsidir. N uzunluğunda bir sətir n var! permutasiya. Burada verilən sətri yenidən düzəldən və leksikoqrafiya cəhətdən növbəti permutasiyanı qaytaran next_permute () funksiyasından istifadə edirik.

The "Döndür ()" funksiya bir vektor / sətrin elementlərini döndərir ki, ötürülən orta element birinci olsun. Məsələn, "abc" üçün ortanı ikinci element olaraq döndürmək çağırırıqsa, sətir "bca" olur. Yenidən ikinci element olaraq ortayla döndür çağırırıqsa, simli "kabin" olur.

  • İstifadəçidən giriş sətirlərini və başqa bir boş sətri ans götürün.
  • Str ölçüsü 0 olduqda ans bir permütasiyaya malikdir (“ans” uzunluğu n-dir).
  • “Ans” sətrinin əvvəlindəki bütün simvolları bir-bir hərəkət etdirin.
  • İlk işarəni str-dən çıxarın və “ans” -ə əlavə edin.
  • Sətri bir char sola çevirin.

Həyata keçirilməsi

STL istifadə edərək verilən bir simli permutasiyaları üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;


void permute(string s, string ans)
{
  if(s.size()==0)
  {
    cout<<ans<<endl;
    return;
  }
  for(int i=0;i<s.size();i++)
  {
    permute(s.substr(1),ans+s[0]);
    rotate(s.begin(),s.begin()+1,s.end());
  }
}

int main()
{
  string s;
  cin>>s;
  permute(s,"");
  return 0;
}

STL istifadə edərək verilən bir simli permutasiyaları üçün Java proqramı

import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static String leftrotate(String str)
    {
            String ans = str.substring(1) + str.substring(0, 1);
            return ans;
    }
    public static void permute(String s, String ans)
    {
            if(s.length()==0)
            {
                    System.out.println(ans);
                    return;
            }
            for(int i=0;i<s.length();i++)
            {
                    permute(s.substring(1),ans+s.charAt(0));
                    s = leftrotate(s);
            }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        permute(s,"");
    }
}




cup
cup
cpu
upc
ucp
pcu
puc

STL istifadə edərək verilən bir simli permutasiyaları üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n!) hara n verilən sətrin ölçüsüdür. Burada verilən “s” sətrinin bütün permutasiyasını çap edirik.

Kosmik Mürəkkəblik

O (n) hara n verilən sətrin ölçüsüdür. Bu boşluğu çap etmədən əvvəl müəyyən bir permütasiyanı təmsil edən bir simli saxlamaq üçün istifadə edirik.

Translate »