Lexicographically minimal string rotation
કોમ્પ્યુટર વિજ્ઞાનમાં, લેક્સિકોગ્રાફિકલી મિનિમલ સ્ટ્રિંગ રોટેશન અથવા લેક્સિકોગ્રાફિકલી લીસ્ટ સર્ક્યુલર સબસ્ટ્રિંગ એ આવા તમામ પરિભ્રમણોનો સૌથી નીચો લેક્સિકોગ્રાફિક ક્રમ ધરાવતી સ્ટ્રિંગનું પરિભ્રમણ શોધવાની સમસ્યા છે. ઉદાહરણ તરીકે, "બાબાક્કાડ" નું લેક્સિકોગ્રાફિક રીતે ન્યૂનતમ પરિભ્રમણ "અકાડાડબ" હશે. શબ્દમાળા માટે બહુવિધ લેક્સિકોગ્રાફિક રીતે ન્યૂનતમ પરિભ્રમણ શક્ય છે, પરંતુ મોટાભાગની એપ્લિકેશનો માટે આનાથી કોઈ ફરક પડતો નથી કારણ કે પરિભ્રમણ સમકક્ષ હોવા જોઈએ. શબ્દકોષીય રીતે ન્યૂનતમ પરિભ્રમણ શોધવું એ તારને સામાન્ય બનાવવાની રીત તરીકે ઉપયોગી છે. જો શબ્દમાળાઓ આલેખ જેવી સંભવિત સમરૂપ રચનાઓનું પ્રતિનિધિત્વ કરે છે, તો આ રીતે સામાન્યીકરણ સરળ સમાનતા તપાસ માટે પરવાનગી આપે છે. ગોળાકાર શબ્દમાળાઓ સાથે વ્યવહાર કરતી વખતે એક સામાન્ય અમલીકરણ યુક્તિ એ છે કે શબ્દમાળા સૂચકાંકો પર મોડ્યુલર અંકગણિત કરવાને બદલે શબ્દમાળાને પોતાની સાથે જોડવી. અલ્ગોરિધમ્સ નિષ્કપટ અલ્ગોરિધમ શબ્દમાળાના લેક્સિકોગ્રાફિકલી ન્યૂનતમ પરિભ્રમણને શોધવા માટેનું નિષ્કપટ અલ્ગોરિધમ એ સૌથી લેક્સિકોગ્રાફિકલી ન્યૂનતમ પરિભ્રમણનો સામનો કરતી વખતે ક્રમિક પરિભ્રમણ દ્વારા પુનરાવર્તન કરવાનું છે. જો શબ્દમાળા લંબાઈની હોય, તો આ અલ્ગોરિધમ સૌથી ખરાબ કિસ્સામાં સમયસર ચાલે છે. બૂથનો અલ્ગોરિધમ બૂથ (1980) દ્વારા એક કાર્યક્ષમ અલ્ગોરિધમનો પ્રસ્તાવ મૂકવામાં આવ્યો હતો. અલ્ગોરિધમ ક્નુથ-મોરિસ-પ્રેટ સ્ટ્રિંગ સર્ચ અલ્ગોરિધમમાંથી સુધારેલા પ્રીપ્રોસેસિંગ કાર્યનો ઉપયોગ કરે છે. શબ્દમાળા માટે નિષ્ફળતા કાર્ય સામાન્ય તરીકે ગણવામાં આવે છે, પરંતુ ગણતરી દરમિયાન શબ્દમાળા ફેરવવામાં આવે છે તેથી કેટલાક સૂચકાંકો આસપાસ લપેટી લેતાં એક કરતા વધુ વખત ગણતરી કરવી આવશ્યક છે. એકવાર નિષ્ફળતા કાર્યના તમામ સૂચકાંકોની સ્ટ્રિંગને ફરીથી ફર્યા વિના સફળતાપૂર્વક ગણતરી કરવામાં આવે, ત્યારે ન્યૂનતમ લેક્સિકોગ્રાફિક પરિભ્રમણ જોવા મળે છે અને તેનો પ્રારંભિક સૂચકાંક પાછો આવે છે. અલ્ગોરિધમનો સચોટતા સમજવી થોડી મુશ્કેલ છે, પરંતુ તેનો અમલ કરવો સરળ છે. ડેફ લીસ્ટ રોટેશન (s: str)-> int: "બૂથનું લેક્સિકોગ્રાફિકલી મિનિમલ સ્ટ્રિંગ રોટેશન અલ્ગોરિધમ". n = લેન (s) f = [-1] * (2 * n) k = 0 જે માટે શ્રેણીમાં (1,2 * n): i = f [j-k-1] જ્યારે i! =-1 અને s [j% n]! = s [(k + i + 1)% n]: જો s [j% n] <s [(k + i + 1)% n]: k = j-i = f [i] જો i = = અને s [j% n] = s [(k + i + 1)% n]: જો s [j% n] <s [(k + i + 1)% n]: k = બૂથનો અલ્ગોરિધમ સમયસર ચાલે છે, સ્ટ્રિંગની લંબાઈ ક્યાં છે. અલ્ગોરિધમ સૌથી ખરાબ કિસ્સામાં મોટાભાગની સરખામણીઓ કરે છે, અને નિષ્ફળતા કાર્ય કોષ્ટકને પકડી રાખવા માટે લંબાઈની સહાયક મેમરીની જરૂર પડે છે. શીલોચના ફાસ્ટ કેનોનાઇઝેશન એલ્ગોરિધમ શીલોચે (1981) પ્રદર્શનની દ્રષ્ટિએ બૂથના પરિણામમાં સુધારો કરતા એક અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો. એવું જોવામાં આવ્યું હતું કે જો લંબાઈની દોરીના સમાન લેક્સિકોગ્રાફિક રીતે ન્યૂનતમ પરિભ્રમણ હોય, તો સ્ટ્રિંગમાં લંબાઈના સમાન સબસ્ટ્રિંગ્સ હોવા જોઈએ. અલ્ગોરિધમને સૌથી ખરાબ કિસ્સામાં માત્ર સરખામણીઓ અને સતત જગ્યાની જરૂર પડે છે. અલ્ગોરિધમ બે તબક્કામાં વહેંચાયેલું છે. પ્રથમ તબક્કો એક ઝડપી ચાળણી છે જે એવા સૂચકાંકોને નકારી કાઢે છે જે દેખીતી રીતે લેક્સિકોગ્રાફિકલી ન્યૂનતમ પરિભ્રમણ માટે પ્રારંભિક સ્થાનો નથી. બીજો તબક્કો પછી બાકી રહેલા સૂચકાંકોમાંથી લેક્સિકોગ્રાફિકલી ન્યૂનતમ પરિભ્રમણ પ્રારંભ સૂચકાંક શોધે છે. ડુવલનું લિન્ડન ફેક્ટરાઇઝેશન એલ્ગોરિધમ ડુવલ (1983) એ એક કાર્યક્ષમ અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો જેમાં સ્ટ્રિંગના ઘટક લિન્ડન શબ્દોમાં ફેક્ટરાઇઝેશનનો સમાવેશ થાય છે, જે સતત મેમરીની જરૂરિયાત સાથે રેખીય સમયમાં ચાલે છે. વેરિયન્ટ્સ શિલોચ (1979) એ સામાન્યીકરણની જરૂરિયાત વિના સમાનતા માટે બે ગોળાકાર શબ્દમાળાઓની અસરકારક રીતે તુલના કરવા માટે એક અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો. એક વધારાનો ઉપયોગ જે અલ્ગોરિધમમાંથી ઉદ્ભવે છે તે પુનરાવર્તન વિના ચોક્કસ રાસાયણિક માળખાઓની ઝડપી પેઢી છે. લિન્ડન શબ્દ ક્નુથ-મોરિસ-પ્રેટ અલ્ગોરિધમ સંદર્ભો શબ્દમાળાઓ પરની સમસ્યાઓ પણ જુઓ લેક્સિકોગ્રાફી ઉદાહરણ કોડ સાથેના લેખો