Last active
February 13, 2017 13:50
-
-
Save sushiljainam/edb99d09228824a18bf3f17573c86a7e to your computer and use it in GitHub Desktop.
find alphabetical rank of a name
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* @Author: Sushil Jain | |
* @Date: 2017-02-13 17:06:37 | |
* @Last Modified by: csnodejs4 | |
* @Last Modified time: 2017-02-13 19:19:49 | |
*/ | |
'use strict'; | |
var input = "sushil"; | |
console.time('timeTaken'); | |
var rank = findRankByString(input); | |
console.timeEnd('timeTaken'); | |
console.log(rank); | |
function findRankByString (input) { | |
if (input.length<=1) { | |
return 1; | |
}; | |
var charsName = []; | |
for (var i = 0; i < input.length; i++) { | |
charsName.push(input[i]); | |
}; | |
// console.log(charsName); | |
var sortedChars = []; | |
sortedChars = copyArray(charsName); | |
for (var i = 1; i < charsName.length; i++) { | |
for (var j = i; j > 0; j--) { | |
if (sortedChars[j-1]>sortedChars[j]) { | |
var t = sortedChars[j]; | |
sortedChars[j] = sortedChars[j-1]; | |
sortedChars[j-1] = t; | |
}; | |
} | |
}; | |
// console.log(charsName); | |
// console.log(sortedChars); | |
var output = findPartialByCharsSorted(charsName, sortedChars); | |
return output; | |
function findPartialByCharsSorted (chars, sortedChars, combSumInit) { | |
var tChar = chars[0]; | |
var combSum = combSumInit || 0; | |
var len = sortedChars.length; | |
if (len<=0) {return combSum}; | |
for (var j = 0; j < len; j++) { | |
// console.log('loop1') | |
var doneChars = []; | |
for (var i = 0; i < sortedChars.length; i++) { | |
// console.log('loop2') | |
if(tChar == sortedChars[i]) { | |
chars.splice(0, 1) | |
sortedChars.splice(i, 1); | |
// console.log(chars, sortedChars, combSum, doneChars) | |
return findPartialByCharsSorted(chars, sortedChars, combSum); | |
// break; | |
} else if ( !charInArray(sortedChars[i], doneChars)){ | |
var temp = copyArray(sortedChars); | |
temp.splice(i,1); | |
// console.log('-->',combSum, doneChars); | |
combSum += permuteOver(temp); | |
doneChars.push(sortedChars[i]); | |
} | |
}; | |
}; | |
// return combSum; | |
} | |
function permuteOver (chars) { | |
var n = chars.length; | |
var freq = {}; | |
var deno = 1; | |
if(n<=1) {return 1}; | |
for (var i = 0; i < chars.length; i++) { | |
if (freq[chars[i]]) { | |
freq[chars[i]]++; | |
} else{ | |
freq[chars[i]] = 1; | |
} | |
}; | |
for(var key in freq) { | |
if(freq[key]>1){ | |
deno *= factorial(freq[key]); | |
} | |
}; | |
return factorial(n)/deno; | |
} | |
function copyArray (arr) { | |
var t = []; | |
for (var i = 0; i < arr.length; i++) { | |
t.push(arr[i]); | |
}; | |
return t; | |
} | |
function charInArray (c, arr) { | |
for (var i = 0; i < arr.length; i++) { | |
if(c==arr[i]){ | |
return true; | |
} | |
}; | |
} | |
function factorial(x) { | |
if(x==0) { | |
return 1; | |
} | |
return x * factorial(x-1); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment