일치하는 유한 자연수 시리즈

Question

유한 번호 natural number 시리즈를 정규식과 어떻게 일치시킬 수 있습니까?

그래서, 요구 사항은 :

• 문자열 1
• (제 제외한) 각각의 수는 이전의 수 + 1
동일하다 (분리 등) 번호 및 스페이스
• 제 번호가 포함

은 일치해야합니다

,691,363,210

• 1
• 1 2
• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
에서 필연적 번호
• 긴 시리즈 1

일치하면 안 1,000^10 :

• `
• 1 2 3 4 5 6 6

1 3 4

정규식 몇 가지 요구 사항이 있다는 것을 옆 :

• 는 하나의 원샷 표현, 그리고 지침
의주기 조건 알고리즘 베일해야
• perl 정규 표현식

의 모든 기능을 사용할 수 있습니다.

정규 표현식이 실제로 게으르다는 것이 확실하지 않기 때문에 그렇다면 위대 할 것입니다. 자연수 시리즈는 숫자 이론에서 본래의 의미이기 때문에 비 유한입니다.

그리고 마지막 하나. 그 직업에 대해 잘못된 도구를 사용하고있는 이 아닌입니다. 그것은 실제 프로그래밍 작업이 아닙니다.

Answer 1

당신이 이동합니다. Perl v5.10에서 v5.14까지 테스트되었습니다. 키는 재귀 패턴이며 여기에서 우리는 (?&Sequence) 규칙을 재귀합니다. 이것은 유도에 의한 증거의 일부입니다.

bigint은 실제로 1 .. 10**10_000에서 시퀀스를 생성하고자하는 경우에 대비해 제공됩니다. 플랫폼에 따라 32 비트 또는 64 비트 시스템 고유의 int로 제한 할 수 있으면 상당히 빠르게 실행됩니다. 실행이 생산

#!/usr/bin/env perl 
use v5.10; 
use bigint; # only if you need stuff over maxint 

my $pat = qr{ 
    ^
    (?= 1 \b) 
    (?<Sequence> 
     (?<Number> \d+) 
     (?: 
      \s+ 
      (??{ "(?=" . (1 + $+{Number}) . ")" }) 
      (?&Sequence) 
     )? 
    ) 
    $ 
}x; 

# first test embedded data 
while (<DATA>) { 
    if (/$pat/) { 
     print "PASS: ", $_; 

    } else { 
     print "FAIL: ", $_; 
    } 
} 

# now generate long sequences 
for my $big (2, 10, 25, 100, 1000, 10_000, 100_000) { 
    my $str = q(); 
    for (my $i = 1; $i <= $big; $i++) { 
     $str .= "$i "; 
    } 
    chop $str; 
    if ($str =~ $pat) { 
     print "PASS: "; 
    } else { 
     print "FAIL: "; 
    } 
    if (length($str) > 60) { 
     my $len = length($str); 
     my $first = substr($str, 0, 10); 
     my $last = substr($str, -10); 
     $str = $first . "[$len chars]" . $last; 
    } 
    say $str; 

} 


__END__ 
5 
fred 
1 
1 2 3 
1 3 2 
1 2 3 4 5 
1 2 3 4 6 
2 3 4 6 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
1 2 3 4 5 6 6 

:

FAIL: 5 
FAIL: fred 
PASS: 1 
PASS: 1 2 3 
FAIL: 1 3 2 
PASS: 1 2 3 4 5 
FAIL: 1 2 3 4 6 
FAIL: 2 3 4 6 
PASS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
FAIL: 1 2 3 4 5 6 6 
PASS: 1 2 
PASS: 1 2 3 4 5 6 7 8 9 10 
PASS: 1 2 3 4 5 [65 chars]2 23 24 25 
PASS: 1 2 3 4 5 [291 chars] 98 99 100 
PASS: 1 2 3 4 5 [3892 chars]8 999 1000 
PASS: 1 2 3 4 5 [588894 chars]999 100000 

을 이기적를 보이는 위험에는 이런 종류의 물건을 커버 a book있다. 제 5 장 "팬시 패턴"에 대한 내용은 프로그래밍 Perl, 4ᵗʰ edition을 참조하십시오. "명명 된 그룹", "재귀 패턴"및 "문법 패턴"에 대한 새로운 섹션을 확인하십시오. 이 책은 프린터에 있으며 하루나 이틀 안에 전자 방식으로 사용할 수 있어야합니다.

Answer 2

regexes는 주로 텍스트와 일치하기 때문에 요구 사항을 fullfil하는 패턴이 있다고 생각하지 않습니다. 당신이 계산을 수행 자신의 자동 기계를 만들 수 있지만

일치, 또는 당신은 단순히 (perl에서) 다음 정규식

Answer 3

을 시도해보십시오 방법이 더 효율적이어야 번호, 반복 동안 아무 계산도 없다 :

m/\A((??{ our $i += 1 })(?>\s*))+\Z/ 

---

시험 :의

내용:

use warnings; 
use strict; 

while (<DATA>) { 
    chomp; 
    our $i = 0; 
    printf qq[%s\n], $_ if m/\A((??{ our $i += 1 })(?>\s*))+\Z/; 
} 

__DATA__ 
0 
2 
1 
1 3 4 
1 2 
1 2 3 4 5 6 6 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
2 1 
1 2 3 4 5 7 
1   2   3  

는 스크립트를 실행

perl script.pl 

그리고 결과 : 여기

1 
1 2 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
1   2   3