java - Count All Permutations Where No Two Adjacent Characters Are the Same -

-

given sequence contains various amounts of numbers 1, 2, 3, , 4 (examples: 13244, 4442, etc), want count permutations such no 2 adjacent numbers same. believe o(n! * n) , want know if there better 1 out there. have ideas?

 class ideone     {         static int permutationcount++;         public static void main(string[] args) {             string str = "442213";             permutation("", str);             system.out.println(permutationcount);         }          private static void permutation(string prefix, string str) {             int n = str.length();             if (n == 0){                 boolean bad = false;                 //check whether there repeating adjacent characters                 for(int = 0; < prefix.length()-1; i++){                     if(prefix.charat(i)==prefix.charat(i+1))                         bad = true;                 }                 if(!bad){                     permutationcount++;                 }             }             else {                 //recurse through permutations                 (int = 0; < n; i++)                     permutation(prefix + str.charat(i), str.substring(0, i) + str.substring(i+1, n));             }         }     }

i understand question this: given string containing numbers 1,2,3,4 - how many permutations of these characters exist when put them string again there won't same adjecent numbers.

i suggest approach:

  l - length of string   n1 - how many times 1 repeated, n2 - how many times 2 repeated etc.    p - number of possible permutations   p = l! / (n1!*n2!*n3!*n4!)    c - number of solutions fitting constraint   c = p - start permutations    substract permutations have 11 in (just take 11 1 number)   c = c - (l - 1)! / ((n1 - 1)! * n2! * n3! * n4!)    ... same 22 ...    add permutations have both 11 , 22 in (because have substracted them twice, need add them)   c = c + (l - 2)! / ((n1 - 1)! * (n2 - 1)! * n3! * n4!)    ... repeat previous steps 33 , 44 ...

Comments

Post a Comment

Popular posts from this blog

c++ - QTextObjectInterface with Qml TextEdit (QQuickTextEdit) -

-
i registred handler simple qtextobjectinterface , draws 10x10 red rectangle. when used qtextedit in normal qwidget app, worked. when used qquicktextedit (textedit qml component) in qt quick app, doesn't worked (nothing drawed, rectangle in textedit reserved, because when change cursor position, notice there something, empty space, nothing drawed. qtextobjectinterface intrinsicsize method called (that explains why see there empty space 10x10), drawobject method isn't. i did research , found problem here: qquicktextedit.cpp qt 5.3.0 sources (line 1821) qsgnode *qquicktextedit::updatepaintnode(qsgnode *oldnode, updatepaintnodedata *updatepaintnodedata) { . . . if (textframe->firstposition() > textframe->lastposition() && textframe->frameformat().position() != qtextframeformat::inflow) { updatenodetransform(node, d->document->documentlayout()->frameboundingrect(textframe).topleft()); c...
Read more

javascript - angular ng-required radio button not toggling required off in firefox 33, OK in chrome -

-
i trying toggle required attribute on radio button using angular show html5 popup. i cannot following code function correctly in firefox 33. function correctly in chrome. required property being toggled via checkbox value, in firefox, when set false radio button still acts required , shows html5 required popup. see plnkr below example doesn't work me in ff 33. <!doctype html> <html> <head> <script data-require="angular.js@*" data-semver="1.3.1" src="//code.angularjs.org/1.3.1/angular.js"></script> <link href="style.css" rel="stylesheet" /> <script src="script.js"></script> </head> <body ng-app="myapp"> <script> angular.module('myapp',[]) .controller('mycontroller',['$scope',function($scope) { $scope.foorequired=true; $scope.submitform = function() { $scope.submitmessage = ...
Read more

xcode - Swift Playground - Files are not readable -

-
Image
files not readable in swift playground . how make files readable? same code runs on xcode terminal app, fails on swift playground. demo code below. import foundation println("hello, world!") var fname:string = "/users/holyfield/desktop/com.apple.iconcomposer.plist" var fm:nsfilemanager = nsfilemanager.defaultmanager() if(fm.fileexistsatpath(fname)){ println("file exists") if(fm.isreadablefileatpath(fname)){ println("file readable") var fd:nsdata? = nsdata(contentsoffile: fname) println(fd?.length) let pl = nsdictionary(contentsoffile: fname) println(pl?.count) println(pl?.allkeys) }else{ println("file not readable") } } else{ println("file not exists") } sample images: i have thank nate cook first quick response , solid answer. just case share answer post, title misleading. see nate's answer here: https://stackoverf...
Read more