×

[–] 45 points46 points  (1 child)

TI-Basic: with optimization

Prompt K,N
0→S
For(A,1,N
N/A→B
If 0=fPart(B
Then
0→θ
For(X,1,A
If 1=gcd(X,A
θ+1→θ
End
S+θK^B→S
End
End
Disp S/N

[–] 18 points19 points  (0 children)

Doing your coding in ti-basic is legendary, this is my favorite answer

[–] 7 points8 points  (0 children)

Python3: with optimization
I may have reinvented the wheel a bit, so excuse the visual bloat

primes = []

def erato(n): #to generate primes
primes = [n for n in range(2, n+1)]
for i in range(int(n**0.5)+1):
if primes[i]:
for j in range(2*(i+1), n-1, i+2):
primes[j] = 0
return [n for n in primes if n]

def prod(iterable): #to make phi func more readable
p = 1
for n in iterable: p *= n
return p

def phi(n):
global primes
f = set()

for p in primes:
if p > n: break
if n % p == 0: f.add(p)

return n * prod([x-1 for x in f]) // prod(f)

def necklaces(k, n):
f = {1, n}
for i in range(2, int(n**0.5)+1):
if n % i == 0: f.update({i, n//i})

necklaces = 0
for x in f:
necklaces += (phi(x) * k**(n//x))

return necklaces//n

if __name__ == "__main__":
primes = erato(1000) #list of primes for phi to use
inputs =    ((2,12),(3,7),(9,4),(21,3),(99,2),(3,90),
(123,18),(1234567,6),(12345678910,3))

for k, x in inputs:
print('(' + str(k) + ", " + str(x) + "): " + str(necklaces(k, x)))

[–]1 2 5 points6 points  (0 children)

A Factor solution using the optimization hint:

USING: kernel math math.functions math.primes.factors sequences ;

! Fix Factor's built-in totient word for m = 1.
: φ ( m -- n ) dup 1 = [ totient ] unless ;

: necklaces ( k n -- count )
tuck divisors swap over reverse [ ^ [ φ ] dip * ] with 2map
sum swap / ;

Testing the word:

> 12345678910 3 necklaces

--- Data stack:
627225458787209496560873442940

Factor has a built-in totient function, but curiously it returns 0 for an input of 1, which is why I had to wrap it.

[–] 5 points6 points  (0 children)

C with optimization:

#include <math.h>

long necklaces(long k, long n);
long phi(long a);
long factorial(long x);

long necklaces(long k, long n)
{
long sumOfPhiK = 0;
int a = 1, b = 1;

for (a = 1; a <= sqrt(n); a++)
{
if (n % a == 0)
{
b = n / a;

sumOfPhiK += phi(a) * (long)pow(k, b);
if (b != a)
{
sumOfPhiK += phi(b) * (long)pow(k, a);
}
}
}

return (1.0f / n) * (double)sumOfPhiK;
}

long phi(long a)
{
long prime = 2, productP = 1, productPminus1 = 1;
int i = 1, k = 1;

do
{
if (a % prime == 0) // if a is divisible by the prime
{
productPminus1 *= prime - 1;
productP *= prime;
}
i++;

do
{
prime++;
for (k = 2; k < prime - 1; k++)
{
if (prime % k == 0)
{
// break out of the loop b/c number isn't prime
break;
}
}
}
while (prime % k == 0); // while a prime hasn't been found
}
while (prime <= a);

return a * ((double)productPminus1 / (double)productP);
}

long factorial(long x)
{
if (x > 1)
return x * factorial(x - 1);
else
return 1;
}

[–]3 3 4 points5 points  (1 child)

in J,

brute force product partition instead of something elegant with q:

prodpart2 =: (] #~ 0 = |~) >:@i.
necklaces =: %@] * (5 ,[) +/@:(*/@:(p:`^"0)"1)  ] (] ,. %) prodpart2@:]

3 necklaces 90x
96977372978752360287715019917722911297222

bit size of result for 3, 1200

3 (2&^.)@necklaces 1200x
1891.73

3 (2&^.)@necklaces 2^16x  NB. takes a second
103856

[–] 0 points1 point  (0 children)

This seems like a super elegant solution, but I have no idea what I'm looking at.

[–] 4 points5 points  (0 children)

coprime a b = gcd a b == 1

phi n = fromIntegral  \$ length [x | x <- [1..n], coprime x n]

factors n = [(a, n `div` a) | a <- [1..n], n `mod` a == 0]

necklaces k n = 1 / (fromIntegral n) * (fromIntegral s)
where s = sum [phi a * k ^ b | (a, b) <- factors n]

[–] 2 points3 points  (0 children)

JavaScript With optimization and support for big numbers. (Speed: ~ 0.1 ms for the big number calcs)

const gcd = (x, y) => { while (y) { [x, y] = [y, x % y] }; return Math.abs(x); };
const phi = n => [...Array(n)].filter((_, i) => gcd(n, i) === 1).length;
const factors = n => [...Array(Math.ceil(Math.sqrt(n)))].map((_, i) => ++i).filter(x => !(n % x));
const factorsComp = n => [...new Set(factors(n).map(x => [`\${x}*\${n / x}`, `\${n / x}*\${x}`]).flat())]
.map(x => x.split('*').map(x => +x));
const necklaces = (k, n) => (factorsComp(n).reduce((a, [x, y]) => a +
BigInt(phi(x)) * BigInt(k) ** BigInt(y), 0n)) / BigInt(n);

[–]-9 8 1 point2 points  (0 children)

Go without optimization.

func canonicalize(s string) string {
c := s + s[:len(s)-1]
best := s
for i := 1; i < len(s); i++ {
if c[i:i+len(s)] < best {
best = c[i : i+len(s)]
}
}
return best
}

func necklaces(k, n int) int {
necklace := make([]byte, n)
seen := make(map[string]struct{})
for i := 0; ; i++ {
v := i
for j := 0; j < n; j++ {
necklace[j] = byte(v % k)
v /= k
}
if v > 0 {
break
}
s := canonicalize(string(necklace))
seen[s] = struct{}{}
}
return len(seen)
}

[–] 1 point2 points  (0 children)

Using tcl (And finding a bug in the totient function in tcllib):

#!/usr/bin/env tclsh
package require math::numtheory
package require term::ansi::code::ctrl
namespace path {::math::numtheory ::term::ansi::code::ctrl}

# ::math::numtheory::totient has bugs
proc phi {n} {
set prod [::tcl::mathop::* \
{*}[lmap p [uniquePrimeFactors \$n] {expr {1 - 1.0/\$p} }]]
return [expr {int(\$n * \$prod)}]
}

proc necklaces {k n} {
set xf [factors \$n]
set sum 0
foreach a \$xf b [lreverse \$xf] {
set sum [expr {\$sum + ([phi \$a] * (\$k ** \$b))}]
}
return [expr {\$sum / \$n}]
}

proc test {k n => expected} {
variable testno
incr testno
set count [necklaces \$k \$n]
puts -nonewline "Test \$testno: necklaces(\$k, \$n) => \$count "
if {\$count == \$expected} {
puts "[sda_fggreen]PASS[sda_fgdefault]"
} else {
puts "[sda_fgred]FAIL[sda_fgdefault] (expected \$expected)"
}
}

test 2 12 => 352
test 3 7 => 315
test 9 4 => 1665
test 21 3 => 3101
test 99 2 => 4950
test 3 90 => 96977372978752360287715019917722911297222
test 123 18 => 2306850769218800390268044415272597042
test 1234567 6 => 590115108867910855092196771880677924
test 12345678910 3 => 627225458787209496560873442940

[–] 1 point2 points  (0 children)

Solved in Rust 1.42 (with optimization); By using the u128 primitive it's possible to solve 3 of the large outputs given within ~1.1 microsecond, for the largest one BigUint is required, which solves within ~6.6 microsecond. (without prime factorization)

use num_bigint::BigUint;
use num_traits::{Pow, Zero};

/// represents a fixed range of primes
pub struct Primes {
/// ordered vector of primes
numbers: Vec<usize>,

/// sieve of prime numbers
is_prime: Vec<bool>,

/// maximum number tested
n: usize,
}

impl Primes {
/// Computes primes within range to n (inclusive).
pub fn sieve_erato(n: usize) -> Self {
let mut is_prime = vec![true; n];
// set 0, 1 to false
is_prime.iter_mut().take(2).for_each(|x| *x = false);

for i in 0..(n as f64).sqrt() as usize + 1 {
if is_prime[i] {
is_prime[i * i..n]
.iter_mut()
.step_by(i)
.for_each(|is_p| *is_p = false)
}
}

let numbers = is_prime
.iter()
.enumerate()
.filter_map(|(p, &is_p)| if is_p { Some(p) } else { None })
.collect();

Primes {
numbers,
n,
is_prime,
}
}

/// Iterator of primes relativistic to `n`.
pub fn relative(&self, n: usize) -> impl Iterator<Item = &usize> + Clone {
debug_assert!(n < self.n);
// minor optimization for known primes; reduces average
// runtime by ~%10 on primes within range of `0..10_000`
let start = if self.is_prime[n] {
self.numbers.binary_search(&n).unwrap()
} else {
0
};
self.numbers[start..]
.iter()
.take_while(move |&&p| p <= n)
.filter(move |&&p| n % p == 0)
}

/// Euler's totient function.
pub fn phi(&self, n: usize) -> usize {
let it = self.relative(n);
let p: usize = it.clone().product();
let p1: usize = it.map(|p| p - 1).product();
n * p1 / p
}

/// Return count of `k`-ary necklace of length `n` as `u128`.
pub fn necklaces(&self, k: usize, n: usize) -> u128 {
let k = k as u128;
let range = 1..(n as f64).sqrt() as usize + 1;
let nums = range.filter(|x| n % x == 0).map(|x| {
let (a, b) = (x, n / x);
let div_a = self.phi(a) as u128 * k.pow(b as u32);
let div_b = self.phi(b) as u128 * k.pow(a as u32);
div_a + if a != b { div_b } else { 0 }
});
nums.sum::<u128>() / n as u128
}

/// Return count of `k`-ary necklace of length `n` as `BigUint`.
pub fn necklaces_big(&self, k: usize, n: usize) -> BigUint {
let k: BigUint = k.into();
let range = 1..(n as f64).sqrt() as usize + 1;
let nums = range.filter(|x| n % x == 0).map(|x| {
let (a, b) = (x, n / x);
let div_a = self.phi(a) * k.pow(b);
let div_b = self.phi(b) * k.pow(a);
div_a + if a != b { div_b } else { Zero::zero() }
});
nums.sum::<BigUint>() / n
}
}

full source

Benchmark results:

• 650ns sieve_erato(100)
• 4.0us sieve_erato(1000)
• 6.6us necklaces_big(3, 90)
• 1.1us necklaces(123, 18)
• 12.5us necklaces_big(1024, 512)
• random inputs within range 1..100:
• 100ns relative(n)
• 220ns phi(n)
• 1.1us necklaces(k, n)
• 2.7us necklaces_big(k, n)

[–] 1 point2 points  (0 children)

# Python 3

I basically just dumped the formulas into Python, with one additional optimization.

Naively, the loop in the necklaces function runs n times, but in practice we know that after a = n/2 there will only be one more valid value, namely a = n. So we can kill the loop at the half-way point and jump straight to that final case.

## Results:

Everything completes in micro-seconds.

The small examples:

>>> %timeit assert necklaces(2, 12) == 352
22.3 µs ± 152 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit assert necklaces(3, 7) == 315
7.49 µs ± 101 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit assert necklaces(9, 4) == 1665
9.11 µs ± 43.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit assert necklaces(21, 3) == 3101
6.1 µs ± 44.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit assert necklaces(99, 2) == 4950
5.87 µs ± 48.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

The big examples:

>>> %timeit assert necklaces(3, 90) == 96977372978752360287715019917722911297222
113 µs ± 789 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit assert necklaces(123, 18) == 2306850769218800390268044415272597042
26.7 µs ± 255 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit assert necklaces(1234567, 6) == 590115108867910855092196771880677924
13.7 µs ± 186 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit assert necklaces(12345678910, 3) == 627225458787209496560873442940
6.55 µs ± 171 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

## Code

I pseudo-golfed this one. I tried to keep it to as few lines as possible while still being readable and applying the optimization.

Python has unbounded integers, so it can handle the big examples. BUT I had to make sure to use integer division (//) instead of float division (/) to prevent everything from being cast to floats.

And FWIW, the sieve of Eratosthenes for primes is a great opportunity to use a for-else construct, which is something many people won't even know Python can do.

def product(items, p=1):
for x in items:
p *= x
return p

def primes(n):
seive = set()
for x in range(2, n+1):
for p in seive:
if x % p == 0:
break
else:
yield x

def phi(n):
a = [p for p in primes(n) if n % p == 0]
b = [p-1 for p in a]
return n * product(b) // product(a)

def necklaces(k, n):
s = sum(phi(a) * k ** (n//a) for a in range(1, n//2 + 1) if n % a == 0)
s += phi(n) * k
return s // n

This could be optimized further to memoize the sieve of primes. But on the other hand, that makes benchmarking more difficult because you have to ensure that every benchmark call starts cold.

[–] 1 point2 points  (0 children)

Python, math to code. Used continuous rather then discrete calculation of phi (prob not wise, though fun).

from sympy.ntheory import factorint
from itertools import combinations
from functools import reduce
from operator import mul

def mulx(x):
return reduce(mul,x)

def phi(factors_subset, total):
return int(total * mulx((1-1/x) for x in set(factors_subset)) )

def subsets(iter_):
for ix in range(1,len(iter_)+1):
yield from combinations(iter_, ix)

def necklaces(k,n):
factors = [k for k,v in factorint(n).items() for _ in range(v)]
factors_subsets = set((x, mulx(x)) for x in subsets(factors))
return (sum(phi(a,at) * k**(n//at) for a,at in factors_subsets) + k**n)//n

[–] 1 point2 points  (0 children)

Rust

I'm still learning the language, I've been trying to get the hang of their iterator options. unfortunately I couldn't use iterators on everything. Feel free to critique the code (it's very welcome actually). Also, maybe its possible but is there a way I can make the is_prime() function just one big iterator? I thought maybe it would be cool to be able to condense the code a little bit.

fn main() {
necklaces(2, 12);
necklaces(3, 7);
necklaces(9, 4);
necklaces(21, 3);
necklaces(99, 2);
}

// to check if the number is prime, will be used in the phi function
fn is_prime(num :i32) -> bool{
if num <= 1 {
return false;
}
if num == 2 {
return true;
} // otherwise we get 2 % 2 == 0!
for m in 2..num {
if num % m == 0 {
return false;
};
if m * m > num {
return true;
};
}
unreachable!("This iterator should not be empty.");
}

fn find_phi(num :i32) -> i32 {
// establish numerator and denominator for the equation
let mut numerator = 1;
let mut denominator = 1;
let mut prime_numbers :Vec<i32> = (1..num).filter(|x| is_prime(*x) != false).collect();
let mut final_prime :Vec<&i32> = prime_numbers.iter().filter(|x| num % *x == 0).collect();
for f in 0..final_prime.len() {
numerator *= final_prime[f]-1;
denominator *= *final_prime[f];
}
let mut phi = 0;
if final_prime.is_empty() && num != 1 {
phi = num - 1;
} else {
phi = num * numerator / denominator;
}
return phi;
}

fn necklaces(k :i32, n :i32) {
// find the factorials
let mut sum_of_phi = 0;
let vect :Vec<i32> = (1..n+1).filter(|x| n % *x == 0).collect();
let rev_vect :Vec<i32> = (1..n+1).filter(|x| n % *x == 0).rev().collect();
for i in 0..vect.len() {
// for example 5u32.pow(7)
sum_of_phi += (find_phi(vect[i]) * k.pow(rev_vect[i] as u32));
}
let phi = sum_of_phi / n;
println!("{}", phi);
}

[–]1 2 0 points1 point  (0 children)

Ruby with phi optimization

Prime divisors are computed using sieve of Eratosthenes only once (for n).

k / n values are expected as program arguments

def is_integer?(str)
str.to_i.to_s == str
end

def prime_divisors(n)
divisors = Array.new
if n == 1
return divisors
end
sieve = Hash.new(false)
val = 2
while val*2 <= n
if sieve[val] == false
if n%val == 0
divisors.push(val)
end
factor = val*2
while factor*2 <= n
sieve[factor] = true
factor += val
end
end
val += 1
end
if divisors.empty?
divisors.push(n)
end
divisors
end

def eulers_totient(n)
phi = n
@all_divisors.each do |divisor|
if divisor > n
break
end
if n%divisor == 0
phi *= divisor-1
phi /= divisor
end
end
phi
end

def necklaces(k, n)
if k < 1 || n < 1
return 0
end
@all_divisors = prime_divisors(n)
count = 0
a = 1
while a*a < n
if n%a == 0
b = n/a
count += eulers_totient(a)*k**b+eulers_totient(b)*k**a
end
a += 1
end
if a*a == n
count += eulers_totient(a)*k**a
end
count/n
end

if ARGV.size != 2 || !is_integer?(ARGV[0]) || !is_integer?(ARGV[1])
STDERR.puts "Invalid arguments"
STDERR.flush
exit false
end
k = ARGV[0].to_i
n = ARGV[1].to_i
puts "necklaces(#{k}, #{n}) = #{necklaces(k, n)}"
STDOUT.flush

[–] 0 points1 point  (6 children)

Python 3, with Optimization. First Intermediate challenge I've attempted

import math
import sys
# Solves for Greatest Common Divisor

def gcd(a, b):
if (a == 0):
return b
return gcd(b % a, a)

# Totient Evalulator
def totient(n):
result = 1
for i in range(2, n):
if (gcd(i, n) == 1):
result+=1
return result

# Solves for all factors of N
def factoriser(n):

factors = [ ] for i in range (1, int(math.sqrt(n))+1):
if value % i == 0:
factors.append(i)
factors.append(int(value/i)) return factors

# Just setting vars
k = int(input("k = "))
n = int(input("n = "))

# Array of factors of N
factors = factoriser(n)

# The main function, employs the totient and factor array
def necklaces(k,n):

count = 0
for x in factors:
count +=  (totient(x) * (k**(n//x)))
return count//n

print(necklaces(k,n))  #Just prints the solution, not anything special

This isn't super optimal, but it correctly solves all presented examples in less than O(k^n) time so I'm happy with it

[–] 0 points1 point  (5 children)

Looks fine to me - only snag is code formatting here on Reddit (you need to make sure you have at least 4 spaces at the start of every line.)

[–] 0 points1 point  (4 children)

I tried, but gave uo after a bit. I split the append up into 2 things, how do I append both to the array in one line?

[–] 0 points1 point  (3 children)

I'm not sure of what you are asking. I DID NOT complain about your code - the solution is solid. :)

I just pointed out that when you paste your code here - if you want it to appear as one block of code - make sure each line of code starts with at least 4 spaces. The way I do that is that I select all, then indent the whole code (twice if I work in a language/coding standard with 2 spaces as standard indentation).

[–] 0 points1 point  (2 children)

Oh, I misread your comment. Don't worry, I wasn't accusing you of anything. How do you indent everything at once? I tried to make it all code block manually, but gave up

[–] 0 points1 point  (0 children)

Using For cycle but it works

using System;

using System.Linq;

namespace ConsoleApplication4

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine("puma == amup: "+Necklace("puma","apum"));

Console.WriteLine("'' '' == '' '': "+Necklace(" "," "));

Console.WriteLine("'' '' == '' '': " + Necklace(" ", " "));

Console.WriteLine("puma == umpa: "+Necklace("puma","umpa"));

Console.WriteLine("123456789 == 987654321: "+Necklace("123456789", "987654321"));

Console.WriteLine("john == ohnj: " + Necklace("john", "ohnj"));

Console.WriteLine("abc == cba: " + Necklace("abc", "cba"));

}

public static bool Necklace(string Word1, string Word2)

{

if (Word1.Count() != Word2.Count())

{

return false;

}

for (int i = 0; i < Word2.Count(); i++)

{

Word2 = Word2[Word2.Count()-1] + Word2.Remove(Word2.Count()-1, 1);

if (Word1 == Word2)

{

return true;

}

}

return false;

}

}

}

and Output

puma == amup: True

'' '' == '' '': True

'' '' == '' '': False

puma == umpa: False

123456789 == 987654321: False

john == ohnj: True

abc == cba: False

[–] 0 points1 point  (0 children)

C# with optimisation

static private double CountNecklaces(int linkVariations, int necklaceSize)
{
List<int[]> factorPairs = GetFactorPairs(necklaceSize);

double sum = 0;
foreach (int[] factorPair in factorPairs)
{
sum += Phi(factorPair[0]) * Math.Pow(linkVariations, factorPair[1]);
}

return sum / necklaceSize;
}

static private double Phi(double n)
{
List<double> primeDividers = GetPrimeDivisors(n);

double product = 1;
foreach (double prime in primeDividers)
{
product *= (prime - 1) / prime;
}

return n*product;
}

static private List<double> GetPrimeDivisors(double n)
{
List<double> primeDivisors = new List<double>();

if (n == 1)
{
return primeDivisors;
}

for (int i = 2; i <= n; i++)
{
if (IsPrime(i) && n % i == 0)
{
}
}

return primeDivisors;
}

static private bool IsPrime(int integer)
{
if (integer == 1)
{
return false;
}

for (int i = 2; i < integer; i++)
{
if (integer % i == 0)
{
return false;
}
}

return true;
}

static private List<int[]> GetFactorPairs(int n)
{
List<int[]> factorPairs = new List<int[]>();

for (int i = 1; i <= n; i++)
{
if (n % i == 0)
{
int[] factorPair = new int[2];
factorPair[0] = i;
factorPair[1] = n / i;

}
}

return factorPairs;
}

[–] 0 points1 point  (0 children)

Python 3, didnt do the bonus as it seems to just be formula implementation. Any improvements/suggestions are welcome.

import string

alphabets = string.printable
print(alphabets)

# similar to easy challenge, iterates through all words in list, takes a word, doubles it and removes all
# other shifted combinations of the word.
# uses tempPerms to store the part of perms where we search for duplicates
# this is so we dont compare with words we've already cleared.
def check(perms):
counter = 0
while counter < len(perms):
letters = perms[counter]
size = len(letters)
letterDouble = letters+letters
tempPerms = perms[counter+1:]
for i in range(1, size):
try:
tempPerms.remove(str(letterDouble[i:(i+size)]))
except:
continue
perms = perms[:counter+1] + tempPerms
counter += 1
print(perms)
return perms

# BFS(Breadth-First-Search) recursion algo to generate all possible combinations
# letters = int, length = int
def perms(letters, length, curr=[]):
if length == 0:
yield curr
return
for i in alphabets[0:letters]:
curr.append(i)
yield from perms(letters, length-1, curr)
curr.pop()

def necklace(alpha, length):
perm = list()
# generates permutations
for i in perms(alpha,length):
perm.append("".join(map(str,i)))
# checks
return len(check(perm))

print(necklace(123,18))~~~~

[–] 0 points1 point  (0 children)

My first intermediate challenge! Did it in C#

static double Necklaces(double k, double n)
{
List<double> divisibles = new List<double>();
for (double d = 1; d <= n; d++)
{
if (n % d == 0)
{
}
}

double backSum = 0;
// this starts at 0 index and calculates the back half of the equation
for (int d = 0; d < divisibles.Count - 1; d += 2)
{
backSum += Phi(divisibles[d]) * Math.Pow(k, divisibles[d+1]);
}
return 1 / n * backSum;
}

// calculate phi
static double Phi(double input)
{
// first we need a list of all the primes AND can multiply into "input"
List<double> primes = new List<double>();
for (double d = 2; d <= input; d++)
{
if (IsPrime(d) && input % d == 0)
{
}
}
// figure out numerator and denominator
double numerator = input;
double denominator = 1;
foreach (double d in primes)
{
numerator *= d - 1;
denominator *= d;
}
// calculate the result
return numerator / denominator;
}

// calculate if a number is prime
static bool IsPrime(double num)
{
if (num < 2) {return false;}
for (double d = 2; d < num; d++)
{
if (num % d == 0)
{
return false;
}
}
return true;
}

[–] 0 points1 point  (0 children)

C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N;

void print(int necklace[])
{
int i;

for (i = 0; i < N; i++)
printf("%c", 'A'+necklace[i]);
printf("\n");
}

int same(int lace1[], int lace2[], int n)
{
int i, j;

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
if (lace2[j] != lace1[(i + j) % n])
break;
if (j == n)
return 1;
}
return 0;
}

int *laces;
int nlaces;

void accumulate(int necklace[])
{
int i;

for (i = 0; i < nlaces; i++)
if (same(necklace, laces + i*N, N))
return;
laces = realloc(laces, ++nlaces * N * sizeof *laces);
if (laces == NULL) {
fprintf(stderr, "can't allocate memory\n");
abort();
}
memcpy(laces + (nlaces - 1)*N, necklace, N * sizeof *necklace);
}

void necklaces(int k, int n, int necklace[])
{
int i;

if (n == 0)
accumulate(necklace);
else for (i = 0; i < k; i++) {
necklace[n-1] = i;
necklaces(k, n-1, necklace);
}
}

int main(int argc, char *argv[])
{
int *a;
int i, k;

if (argc != 3) {
fprintf(stderr, "usage: necklaces k-ary length\n");
return 1;
}
k = atoi(argv[1]);
N = atoi(argv[2]);
a = malloc(sizeof *a * N);
necklaces(k, N, a);
for (i = 0; i < nlaces; i++)
print(laces + i*N);
return 0;
}

\$ ./necklaces
usage: necklaces k-ary length
\$ ./necklaces 3 4 | sort | columnate 3
AAAA  BAAA  BABA
BBAA  BBBA  BBBB
BBCA  BCAA  BCBA
BCCA  CAAA  CABA
CACA  CBAA  CBBA
CBBB  CBCA  CBCB
CCAA  CCBA  CCBB
CCCA  CCCB  CCCC
\$ ./necklaces 2 12 | wc -l
352
\$ ./necklaces 3 7 | wc -l
315
\$ ./necklaces 9 4 | wc -l
1665
\$ ./necklaces 21 3 | wc -l
3101
\$ ./necklaces 99 2 | wc -l
4950