python - How do I find all possible permutations of a string with only single swap? -

-

the complexity should o(n) n length of string. ex: 'abc', answer 'bac', 'cba', 'acb'. 'bca' , 'cab' should not in list 2 swaps required convert 'abc'.

i have made o(n2) algorithm slow.

def f(s):     temp=list(s)     l=[]     in range(len(s)):         j in range(len(s)):             temp=list(s)             temp[i],temp[j]=temp[j],temp[i]             l.append("".join(str(i) in temp))     print set(l)

the number of possible outcomes string (with distinct characters) of length n nc2 = n * (n-1) / 2, since can choose 2 letters @ 2 indices , swap them.

hence, if plan print of outcomes, complexity o(n^2) , o(n) solution not possible.

for duplicate characters, reasoning becomes more complex. suppose there 1 duplicate character repeated k times. there n-k swaps identical. if there 1 character repeated, , repeated k times, number of possibilities nc2 - (n-k). can extended more repeated characters using inclusion-exclusion principle.


Comments

Post a Comment

Popular posts from this blog

java - Run spring boot application error: Cannot instantiate interface org.springframework.context.ApplicationListener -

-
i have spring project , try make use spring boot , run @ embadded tomcat following : https://spring.io/guides/gs/rest-service/ this application //@configuration //@enableaspectjautoproxy @springbootapplication @componentscan(basepackages = "gux.prome") public class application { public static void main(string[] args) { springapplication.run(application.class, args); } } if use maven command: mvn spring-boot:run , project starts fine, need debug , run main method @ intelij, exception occurs: exception in thread "main" java.lang.illegalargumentexception: cannot instantiate interface org.springframework.context.applicationlistener : org.springframework.boot.logging.classpathloggingapplicationlistener @ org.springframework.boot.springapplication.createspringfactoriesinstances(springapplication.java:414) @ org.springframework.boot.springapplication.getspringfactoriesinstances(springapplication.java:394) @ org.springframework.bo...
Read more

python - pip wont install .WHL files -

-
when try install .whl gohike typing cmd c:\users\owner\downloads>pip install ta_lib-0.4.9-cp27-none-win_amd64.whl i print out: `processing c:\users\owner\downloads\ta_lib-0.4.9-cp27-none-win_amd64.whl complete output command python setup.py egg_info: traceback <most recent call last>: file "<string>", line 1, in <module> ioerror: [errno 2] no such file or directory:'c:\\users\\owner\\appdata\\lo cal\\temp\\pip-9gwk2c-build\\setup.py' ----------------------------------------- command "python setup.py egg_info" failed error code 1 in c:\users\owner\ap pdata\local\temp\pip-9gwk2c-build\` the part between pip- , -build in pip-9gwk2c-build different on same file. i asked python 2.7.11 pip 8.0.3 can't install gohike whl of ta-lib 0.4.9 few days ago , decided ask differently. can me! you have outdated pip not understand wheels. wheels not supposed have setup.py inside. try upgrading pip pip in...
Read more

Excel VBA "Microsoft Windows Common Controls 6.0 (SP6)" Location Changes -

-
i have excel workbook used generate quotations customers. there main page user inputs data, , there buttons generate various pdfs , send them customer. however, 1 user consistently getting error preventing generating , sending pdfs. i beleive "microsoft windows common controls 6.0 (sp6)". it's installed on users' computers. on mine, location "c:\windows\syswow64\mscomctl.ocx" on others "c:\windows\system32\mscomctl.ocx" the user experiencing issues on 32-bit machine, "mscomctl.ocx" file should in system32. have manually put in there, , pointed common controls reference in vba it. issue seems keep reverting looking in syswow64. since folder doesn't exist, can't find it, , can't produce pdfs. i thought perhaps issue user running older version of office (2007) there users on 2013 , 2016. thought perhaps mixture of 64-bit , 32-bit users. user gets sent workbook other users (as quotation process goes further, gets passed ...
Read more