Polynomial-Time Algorithm for k-ary Necklaces with Forbidden Patterns:  Exponential to O(n²k)

Sirisha Peddinti

Polynomial-Time Algorithm for k-ary Necklaces with Forbidden Patterns: Exponential to O(n²k)

Authors

Sirisha Peddinti

Keywords:

Terms—combinatorial enumeration, necklaces, pattern avoidance, recursive algorithms, asymptotic analysis, Burnside’s lemma

Abstract

We present a novel recursive enumeration method for kary necklaces that avoid specific forbidden patterns. Traditional brute
force approaches require O(kn) time complexity for necklaces of lengthn over a k-symbol alphabet

References

G. Polya,´ ”Kombinatorische Anzahlbestimmungen fur¨ Gruppen, Graphen und chemische Verbindungen,” Acta Mathematica, vol. 68, no.

, pp. 145–254, 1937.

W. Burnside, ”Theory of Groups of Finite Order,” Cambridge University Press, 1897

Downloads

Published

2025-02-13

How to Cite

Sirisha Peddinti. (2025). Polynomial-Time Algorithm for k-ary Necklaces with Forbidden Patterns: Exponential to O(n²k) . Journal of Computational Analysis and Applications (JoCAAA), 34(2), 249–255. Retrieved from https://www.eudoxuspress.com/index.php/pub/article/view/2941